構文解析手続き
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/01/06 06:27 UTC 版)
最初に、構文解析器は入力バッファから '(' を読み込み、スタックから 'S' を読み込む。表を参照すると、規則2を適用すべきであることがわかる。規則2はスタック上の 'S' を '( S + F )' に書き換え、規則番号を出力する。スタックの内容は次のようになる。 [ (, S, +, F, ), $ ] 次に、入力バッファとスタック双方から '(' を取り除く。 [ S, +, F, ), $ ] 次に、入力バッファには '1' があり、スタックのトップが 'S' であることから規則1が適用されて、スタックのトップが 'F' に書き換えられ、さらに規則3が適用される（適用した規則の番号として 1 と 3 が出力される）。スタックは次のようになる。 [ F, +, F, ), $ ][ 1, +, F, ), $ ] さらに、入力バッファの先頭の '1' と '+' はスタックのトップと同じなので、これらが双方から取り除かれる。スタックは以下のようになる。 [ F, ), $ ] 次に、スタック上の 'F' が '1' に書き換えられ、規則番号3が出力される。そして、'1' と ')' は入力バッファとスタック上でマッチするので取り除かれる。この時点で入力バッファもスタックも '$' だけとなり、構文解析が完了する。 この例では、入力文字列が受容され、以下の規則が順に適用されたことが出力される。 [ 2, 1, 3, 3 ] 以上が左端導出である。ここでの左端導出は以下のように行われた。 S → ( S + F ) → ( F + F ) → ( 1 + F ) → ( 1 + 1 )
※この「構文解析手続き」の解説は、「LL法」の解説の一部です。
「構文解析手続き」を含む「LL法」の記事については、「LL法」の概要を参照ください。
- 構文解析手続きのページへのリンク
