05-01: Introduction to Parsing 語法分析

parser的作用：

05-02: Context Free Grammars 上下文無關文法

CFG（上下文無關文法）回答了一個字符串是否屬于某語言：

CFG的組成：

終止符

非終止符

開始符

生成式

生成式production （非終止符non-terminal -> 終止符terminal）

05-03: Derivations 推導

• 推導是一系列生成
• 推導可以用樹的形式表示
• 一個推導可以定義一棵語法樹，但是一棵語法樹可以定義不同的推導

• 最左推導和最右推導定義同一棵語法樹

05-04: Ambiguity

Ambiguity：一個字符串對應多個語法樹

避免二義性：

方法1：左遞歸寫法

方法2：用Bison中的%定義

06-01: Error Handling

方法1：panic mode

skip input and try to continue

方法2：error production

specify known common mistakes in the grammar

方法3：error correction

try token insertions and deletion

06-02: Abstract Syntax Trees

• AST:

06-03: Recursive Descent Parsing 遞歸下降語法分析

Recursive Descent 是一種通用的語法分析算法。

輸入：token串

Recursive Descent ：判斷是否符合該（上下文無關）語言語法，并構建語法樹

06-04: Recursive Descent Algorithm

遞歸下降具體算法：

從開始符號起，依次遞歸嘗試每一個產生式。若返回匹配，且遍歷到字符串末尾，則成功。

06-04-1: Recursive Descent Limitations

使用Recursive Descent做語法分析時，需轉化左遞歸文法。

左遞歸文法是形如 S->Sa 的文法

左遞歸文法會導致無限循環。因為它本質上是從右到左推導的。而遞歸下降算法是從左到右推導的。

06-05: Left Recursion

將左遞歸文法轉換為右遞歸文法的方法：

隱式左遞歸文法

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的编译原理语法分析_斯坦福大学《编译原理》学习记录 - 第二章：语法分析器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。