前言

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

這些前置知識(shí)在之前的博文都有提起過(guò)

之前的博文目錄

項(xiàng)目的完整代碼在 C2j-Compiler

什么是語(yǔ)法分析？

如果我們把詞法分析看成是組合單詞，輸出單詞流，那么語(yǔ)法分析就可以看作是檢查這些單詞是不是符合語(yǔ)法的過(guò)程。在詞法分析的時(shí)候用正則或者手工比對(duì)來(lái)驗(yàn)證單詞，語(yǔ)法分析則是用上下文無(wú)關(guān)文法 （context-free grammar，CFG）。

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

BNF范式

巴科斯范式（英語(yǔ)：Backus Normal Form，BNF）是一種用于表示上下文無(wú)關(guān)文法的語(yǔ)言。

看一個(gè)例子：

S –> AB
A –> aA | ε
B –> b | bB

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

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

S就是開(kāi)始符號(hào)。

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

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

語(yǔ)法分析的幾種方法

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

之前在學(xué)習(xí)的時(shí)候稍微記錄了一下這幾種方法，在這里就不說(shuō)了

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

自底向上語(yǔ)法分析

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

自底向上的語(yǔ)法分析

一個(gè)自底向上的語(yǔ)法分析過(guò)程對(duì)應(yīng)為一個(gè)輸入串構(gòu)造語(yǔ)法分析書(shū)的過(guò)程，它從葉子節(jié)點(diǎn)開(kāi)始，通過(guò)shift和reduce操作逐漸向上到達(dá)根節(jié)點(diǎn)

自底向上的語(yǔ)法分析需要一個(gè)堆棧來(lái)存放解析的符號(hào)，例如對(duì)于如下語(yǔ)法：

0.  statement -> expr
1.  expr -> expr   factor
2.           | factor
3.  factor ->  ( expr )
4.           | NUM

來(lái)解析1 2

此時(shí)規(guī)約到開(kāi)始符號(hào)，并且輸入串也為空，代表語(yǔ)法解析成功

所以實(shí)現(xiàn)自底向上的語(yǔ)法解析關(guān)鍵就是識(shí)別堆棧上是應(yīng)該進(jìn)行shift還是reduce操作。

• 進(jìn)行暴力匹配，搜索堆棧上的符號(hào)和所有的語(yǔ)法推導(dǎo)式進(jìn)行匹配 x

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

所以接下來(lái)的任務(wù)自然就是構(gòu)建一個(gè)有限狀態(tài)自動(dòng)機(jī)來(lái)能夠指導(dǎo)語(yǔ)法分析器來(lái)進(jìn)行操作。

小結(jié)

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

語(yǔ)法分析就是檢查輸入的Token流是不是符合語(yǔ)法的過(guò)程，而完成這一步驟的語(yǔ)法分析算法，拿自底向上來(lái)說(shuō)，也就是從葉子節(jié)點(diǎn)向上推導(dǎo)成樹(shù)頂端的過(guò)程。

另外我的github博客：https:///