語法分析
上下文無關文法 語法剖析器 |
|---|
| · LL剖析器 |
| · 算符優先剖析器 |
| · LR剖析器 |
| · SLR剖析器 |
| · LALR剖析器 |
在電腦科學和語言學中，語法分析（英語：syntactic analysis，也叫 parsing）是根據某種給定的形式文法對由單詞序列（如英語單詞序列）構成的輸入文字進行分析並確定其語法結構的一種過程。
語法剖析器（parser）通常是作為編譯器或直譯器的組件出現的，它的作用是進行語法檢查、並構建由輸入的單詞組成的數據結構（一般是語法分析樹、抽象語法樹等層次化的數據結構）。語法剖析器通常使用一個獨立的詞法剖析器從輸入字元流中分離出一個個的「單詞」，並將單詞流作為其輸入。實際開發中，語法剖析器可以手工編寫，也可以使用工具（半）自動生成。
語法剖析器分類
語法剖析器的任務主要是確定是否可以以及如何從語法的起始符號推導出輸入符號串（輸入文字），主要可以通過兩種方式完成：
- 自頂向下分析：根據形式語法規則，在語法分析樹的自頂向下展開中搜尋輸入符號串可能的最左推導。單詞按從左到右的順序依次使用。
- 由下而上分析：語法剖析器從現有的輸入符號串開始，嘗試將其根據給定的形式語法規則進行覆寫，最終覆寫為語法的起始符號。
參考文獻
- 書籍
- Chapman, Nigel P., LR Parsing: Theory and Practice（頁面存檔備份，存於互聯網檔案館）, Cambridge University Press, 1987. ISBN 0-521-30413-X.
- Grune, Dick; Jacobs, Ceriel J.H., Parsing Techniques - A Practical Guide（頁面存檔備份，存於互聯網檔案館）, VU University Amsterdam, Amsterdam, The Netherlands. Originally published by Ellis Horwood, Chichester, England, 1990; ISBN 0-13-651431-6.
