言語処理系

言語処理系(compiler 編訳系)の構造

  1. 語句解析
  2. 構文解析
  3. 意味解析
  4. コード生成
編訳系の処理相の間では中間言語による処理結果の受け渡しと 表の参照が行われる。

語句解析(lexical analysis)

名標(identifier) 定数語(literal constant) 基要語 (keyword) などに 分解し素語(lexical token)として認識する。

素語を文字から構成する規則 ... 正規文法(regular grammar)
正規表現 (regular expression)の例

名標
[A-Za-z_][0-9A-Za-z_]*
整定数
[1-9][0-9]*
正規言語は有限オートマトンによって認識できる。 適切な識別のための処理を補う。

構文解析(1)LL(1)解析法など

syntax analysis, parsing (枝付け) 構文解析の結果は 系統木や構文木で表される。
例:if X < Y then MAX := Y else MAX := X

文法にもとづく導出による生成ができるかどうかの解析
解析方法

  • 下降型解析法
    系統木の根から葉に向かって木を構成していく
  • 上昇型解析法
    葉から根に向かう。導出の逆の過程=還元(reduction)
  • 再帰下降型解析法

    開始記号から始めて最左導出を試みる。
    導出での例「式」は最右導出。 最左導出では
    式 => 項 => 項*式 => 係数*式 => 名標*式 => 名標*項 => 名標*係数 => 名標*(式) => 名標*(式+項) => 名標*(項+項) => 名標*(係数+項) => 名標*(名標+項) => 名標*(名標+係数) => 名標*(名標+名標)
    のようになる。
    左再帰的な生成規則がある場合には解析ができなくなる。 この場合、構文規則を書き直して再帰的解析法が使えるように なおす必要がある。

    「式」の構文規則を変更し、再帰的な解析法を適用したプログラム例を示す。

    procedure E();
      begin T();
        while token = '+' do
          begin gettoken(); T() end
      end;
    procedure T();
      begin F();
        while token = '*' do
          begin gettoken(); F() end
      end;
    procedure F();
      begin
        if token = '(' then
          begin gettoken(); E();
            if token <> ')' then error();
          end
        else if token = 'i' then gettoken()
        else error();
      end;
    
    上の例では
     E -> T, E -> T + T,
     T -> F, T -> F * F,
     F -> ( E ), F -> i
    
    のように、構文規則を書き換えている。

    L .. 左から素語を調べる
    L .. 最左導出
    (1) .. 1個の先読み


    予測型解析法

    再帰的手法を用いずに、オートマトンを使って導出を実現する。
    deriveX->Y1Y2...Yk 導出
    error誤り

    LR解析法

    上昇型解析法 ... 素語を読み込みながら構文規則に したがって還元を繰り返す。(shift-reduce parsing)
    shift読み込み
    reduceX->Y1Y2...Yk 還元
    accept受理
    error誤り
    スタック上には記号 X と状態 s を交互に置き、スタックの 最上段にある状態 s と入力素語 a から解析表 A を参照する ことによって動作を決定する。状態遷移は別の解析表 G で 与える。アルゴリズムは以下のとおり。
    repeat
      s:=スタック最上段の状態;
      a:=つぎに調べようとしている素語;
      if A[s,a]=shift then
        begin t:=G[s,a];
          スタックにaとtとをtが最上段に
          くるように押し込み、入力素語列
          からaを取り除く
        end
      else if A[s,a]=reduce X->Y1Y2...Yk then
        begin スタックからk個の状態とk個の
              記号を取り出す;
          u:=スタック最上段の状態;
          t:=G[u,X];
          スタックにXとtとをtが最上段に
          くるように押し込む
        end
      else if A[s,a]=accept then 解析終了
      else 誤り
    forever;
    

    「式」の構文規則としては、

    1. E -> E+T
    2. E -> T
    3. T -> T*F
    4. T -> F
    5. F -> (E)
    6. F -> i

    解析表
    AG
    状態+*()i$+*()i$ETF
    0ss45123
    1sa6
    22s227
    34444
    4ss45823
    56666
    6ss4593
    7ss4510
    8ss611
    91s117
    103333
    115555

    解析例
    スタック素語の列動作
    --------------------------------
    $0i*(i+i)$shift
    $0i5*(i+i)$reduce 6
    $0F3*(i+i)$reduce 4
    $0T2*(i+i)$shift
    $0T2*7(i+i)$shift
    $0T2*7(4i+i)$shift
    $0T2*7(4i5+i)$reduce 6
    $0T2*7(4F3+i)$reduce 4
    $0T2*7(4T2+i)$reduce 2
    $0T2*7(4E8+i)$shift
    $0T2*7(4E8+6i)$shift
    $0T2*7(4E8+6i5)$reduce 6
    $0T2*7(4E8+6F3)$reduce 4
    $0T2*7(4E8+6T9)$reduce 1
    $0T2*7(4E8)$shift
    $0T2*7(4E8)11$reduce 5
    $0T2*7F10$reduce 3
    $0T2$reduce 2
    $0E1$accept

    上の構文規則を yacc で書いて、yacc -v コマンドを用いると y.output というファイルができる。


    意味解析 (semantic analysis)

    名標(identifier)の有効範囲、データの適合性の解析。 一般的には構文解析の中に埋め込まれる。
    宣言の処理
    ブロック構造を持つ言語では、あらたな ブロックに入るたびに名標を管理する表が作成され、ブロック から出る時に消滅する。
    式・文の処理
    データ型の適合性、飛び越し先の適合性。
    記憶場所の割り当て
    プログラムが実行される時の静的な変数領域
    (動的な変数領域の割り当ては実行時支援系によって行われる)

    コード生成

    目的言語(機械語)プログラムの生成。
    例題:yacc を用いて "3の倍数である2進数を判定するプログラム"を書く
    解答例 yacc pof3.y で y.tab.c が作成され、 cc y.tab.c -ly で a.out ができる。