語法分析器

簡介

語法分析器（parser）通常是作為編譯器或解釋器的組件出現的，它的作用是進行語法檢查、并構建由輸入的單詞組成的數據結構（一般是語法分析樹、抽象語法樹等層次化的數據結構）。語法分析器通常使用一個獨立的詞法分析器從輸入字符流中分離出一個個的“單詞”，并将單詞流作為其輸入。實際開發中，語法分析器可以手工編寫，也可以使用工具（半）自動生成。

分類

語法分析器的任務主要是确定是否可以以及如何從語法的起始符号推導出輸入符号串（輸入文本），主要可以通過兩種方式完成：

自頂向下分析：根據形式語法規則，在語法分析樹的自頂向下展開中搜索輸入符号串可能的最左推導。單詞按從左到右的順序依次使用。

自底向上分析：語法分析器從現有的輸入符号串開始，嘗試将其根據給定的形式語法規則進行改寫，最終改寫為語法的起始符号。