前言

在之前完成了詞法分析之后，得到了Token流，那么接下來就是實現(xiàn)語法分析器來輸入Token流得到抽象語法樹 （Abstract Syntax Tree，AST）。但是在完成這個語法分析器不像詞法分析器，直接手擼就好了，還是需要一些前置的知識。

這些前置知識在之前的博文都有提起過

之前的博文目錄

項目的完整代碼在 C2j-Compiler

什么是語法分析？

如果我們把詞法分析看成是組合單詞，輸出單詞流，那么語法分析就可以看作是檢查這些單詞是不是符合語法的過程。在詞法分析的時候用正則或者手工比對來驗證單詞，語法分析則是用上下文無關文法 （context-free grammar，CFG）。

若一個形式文法 G = (N, Σ, P, S) 的產(chǎn)生式規(guī)則都取如下的形式：V -> w，則謂之。其中 V∈N ，w∈(N∪Σ) 。上下文無關文法取名為“上下文無關”的原因就是因為字符 V 總可以被字符串 w 自由替換，而無需考慮字符 V 出現(xiàn)的上下文。一個形式語言是上下文無關的，如果它是由上下文無關文法生成的*

BNF范式

巴科斯范式（英語：Backus Normal Form，BNF）是一種用于表示上下文無關文法的語言。

看一個例子：

S –> ABA –> aA | εB –> b | bB

其中S A B叫作非終結(jié)符，代表可以通過推導產(chǎn)生新的符號，之前在Token類里定義的也有這些非終結(jié)符；a b ε叫作終結(jié)符，表示其無法再通過推導產(chǎn)生新的符號了，ε則表示空；

上面的每一行就是一個產(chǎn)生式規(guī)則，也叫推導式，代表了一種非終結(jié)符的轉(zhuǎn)移方式；

S就是開始符號。

只有終結(jié)符的符號串稱為句子 （sentence）。

比如通過這三個產(chǎn)生式，就可以斷定bbb符合語法規(guī)則。

語法分析的幾種方法

和之前講的一樣，主要分為自頂向上和自底向下兩種

之前在學習的時候稍微記錄了一下這幾種方法，在這里就不說了

遞歸下降和LL(1)語法分析

自底向上語法分析

在這里稍微的再說一下這次語法分析使用的方法，LALR(1)，它也屬于自底向上的分析算法。

自底向上的語法分析

一個自底向上的語法分析過程對應為一個輸入串構(gòu)造語法分析書的過程，它從葉子節(jié)點開始，通過shift和reduce操作逐漸向上到達根節(jié)點

自底向上的語法分析需要一個堆棧來存放解析的符號，例如對于如下語法：

0.  statement -> expr1.  expr -> expr   factor2.           | factor3.  factor ->  ( expr )4.           | NUM

來解析1 2

此時規(guī)約到開始符號，并且輸入串也為空，代表語法解析成功

所以實現(xiàn)自底向上的語法解析關鍵就是識別堆棧上是應該進行shift還是reduce操作。

• 進行暴力匹配，搜索堆棧上的符號和所有的語法推導式進行匹配 x

• 構(gòu)造一個狀態(tài)機來根據(jù)堆棧壓入或彈出后的狀態(tài)來決定是否進行reduce操作

所以接下來的任務自然就是構(gòu)建一個有限狀態(tài)自動機來能夠指導語法分析器來進行操作。

小結(jié)

所謂的前置知識其實也就是了解語法分析在干什么，和大概要怎么干。

語法分析就是檢查輸入的Token流是不是符合語法的過程，而完成這一步驟的語法分析算法，拿自底向上來說，也就是從葉子節(jié)點向上推導成樹頂端的過程。

另外我的github博客：https://dejavudwh.cn/