プッシュダウンオートマトンと解析
構文解析は、文法の生成規則を使用して文字列を導出するために使用されます。文字列の受け入れ可能性をチェックするために使用されます。コンパイラは、文字列が構文的に正しいかどうかをチェックするために使用されます。パーサーは入力を受け取り、解析ツリーを構築します。
パーサーには2つのタイプがあります-
Top-Down Parser −トップダウン解析は、start-symbolで上から開始し、解析ツリーを使用して文字列を導出します。
Bottom-Up Parser −ボトムアップ解析は、文字列で下から始まり、解析ツリーを使用して開始記号に到達します。
トップダウンパーサーの設計
トップダウン構文解析の場合、PDAには次の4つのタイプの遷移があります-
スタックの一番上にあるプロダクションの左側にある非終端記号をポップし、右側のストリングを押します。
スタックの一番上のシンボルが読み取られている入力シンボルと一致する場合は、それをポップします。
開始記号「S」をスタックにプッシュします。
入力文字列が完全に読み取られ、スタックが空の場合は、最終状態「F」に進みます。
例
次の生成規則を使用して、文法Gの式「x + y * z」のトップダウンパーサーを設計します。
P：S→S + X | X、X→X * Y | Y、Y→（S）| id
Solution
PDAが（Q、∑、S、δ、q 0、I、F）の場合、トップダウン構文解析は-です。
（x + y * z、I）⊢（x + y * z、SI）⊢（x + y * z、S + XI）⊢（x + y * z、X + XI）
⊢（x + y * z、Y + XI）⊢（x + y * z、x + XI）⊢（+ y * z、+ XI）⊢（y * z、XI）
⊢（y * z、X * YI）⊢（y * z、y * YI）⊢（* z、* YI）⊢（z、YI）⊢（z、zI）⊢（ε、I）
ボトムアップパーサーの設計
ボトムアップ解析の場合、PDAには次の4つのタイプの遷移があります-
現在の入力シンボルをスタックにプッシュします。
スタックの一番上にあるプロダクションの右側を左側に置き換えます。
スタック要素の最上位が現在の入力シンボルと一致する場合は、それをポップします。
入力文字列が完全に読み取られ、開始記号「S」がスタックに残っている場合にのみ、それをポップして最終状態「F」に移動します。
例
次の生成規則を使用して、文法Gの式「x + y * z」のトップダウンパーサーを設計します。
P：S→S + X | X、X→X * Y | Y、Y→（S）| id
Solution
PDAが（Q、∑、S、δ、q 0、I、F）の場合、ボトムアップ構文解析は−です。
（x + y * z、I）⊢（+ y * z、xI）⊢（+ y * z、YI）⊢（+ y * z、XI）⊢（+ y * z、SI）
⊢（y * z、+ SI）⊢（* z、y + SI）⊢（* z、Y + SI）⊢（* z、X + SI）⊢（z、* X + SI）
⊢（ε、z * X + SI）⊢（ε、Y * X + SI）⊢（ε、X + SI）⊢（ε、SI）