3 0 0 0 意味規則つき正規表現とデータ構造直結型プログラムへの応用
- 著者
- 中田 育男 佐々 政孝 Ikuo Nakata Masataka Sassa 筑波大学電子情報工学系 筑波大学電子情報工学系
- 雑誌
- コンピュータソフトウェア = Computer software (ISSN:02896540)
- 巻号頁・発行日
- vol.3, no.1, pp.47-56, 1986-01-14
正規表現で定義される構造をもった入力を意味処理まで含めて処理しなければならない場合は多い.そのような処理を形式的に取り扱う方法としては文脈自由文法に意味規則を付加した属性文法を使うものがあるが,それでは入力の構造との対応が必ずしもよくないし,処理方法も複雑である.本論文では,このような入力の構造と意味を自然に記述できる意味規則つき正規表現を提案し,その処理法について述べる,最初に,正規表現の中に意味規則を挿入した意味規則つき正規表現を定義し,次に,意味規則つき正規表現から意味処理つき非決定性有限オートマトン(NFA)への変換アルゴリズム,および,NFAから意味処理つき決定性有限オートマトン(DFA)への変換アルゴリズムを与える.最後に,意味規則つき正規表現を,正規表現で定義できる構造をもったデータを処理するプログラム,すなわちデータ構造直結型プログラムに応用するために必要な意味規則および変換アルゴリズムの拡張方法を述べる.
1 0 0 0 OA なかよしグループ問題と属性文法への応用
- 著者
- 山下 義行 佐々 政孝 中田 育男 Yoshiyuki Yamashita Masataka Sassa Ikuo Nakata 筑波大学電子情報工学系 筑波大学電子情報工学系 筑波大学電子情報工学系
- 雑誌
- コンピュータソフトウェア = Computer software (ISSN:02896540)
- 巻号頁・発行日
- vol.4, no.3, pp.212-224, 1987-07-15
「なかよしグループ問題」は,ある条件下での集合の彩色問題を一般化し,より親しみやすい表現に直したものである.この問題ではなかよしグループの子供達に最適な色のキャンディを配ることを考えるが,配色に関する制約条件,局所的な最適条件および大局的な最適条件が絡みあい,必ずしも簡単には解けない.そこで,なかよしグループの中からキーとなる子供達を見つけ出し,その子らについて彩色問題を解くだけで総ての子供達への配色が決まる,という一般的な解法を提案する.応用として,ECLR属性文法に基づくコンパイラ生成系Rieの属性スタック自動割り当てプログラムを作成し,PL/0,Pascalサブセットコンパイラについて最適な割り当てを行った.