语法分析要解决什么
复习
- 字符怎样组成词：把字符流切成词法单元
- 语言与文法：用规则描述语言
- 树：用父子关系表示层次结构
TL;DR
- 语法分析把词法单元序列组织成语法结构
- 它要判断这串词是否符合文法
- 还要给出结构，通常是一棵语法树
- 同一串词，可能有不止一种结构方式
正文
词法分析把字符切成了一个个词，比如 1、+、2、*、3。可这些词只是排成一排，还没有“结构”。把它们组织成有意义的结构，就是语法分析（syntax analysis）的任务。
两个问题
语法分析要同时回答两个问题：
- 合不合法：这串词法单元，符不符合这门语言的文法？
- 什么结构：如果合法，它们是怎样组合起来的？
第 2 点常常被忽略，却至关重要。看 1 + 2 * 3，它不只是五个孤立的词，而是一棵有层次的表达式树：乘法先算，再加。只有拿到这个结构，编译器才知道该先做哪一步运算，才能正确生成代码。
词是平的，结构是立体的
词法分析产出的，是一条平铺的词序列。而语法分析要给它们加上立体的层级关系——谁包含谁、谁先谁后。
这个“立体结构”，通常用语法树来表示：树的叶子是词，内部的节点代表“这里存在一个语法成分”，比如“一个表达式”“一个加法”。从平的序列，到立体的树，是语法分析最大的贡献。
为什么会有多种结构
一个有意思的事实是：同一串词，可能对应不止一种结构。
比如 1 - 2 - 3，既可以理解成 (1 - 2) - 3，也可以理解成 1 - (2 - 3)。两种结构的运算结果不同！到底按哪种，需要语言的规则提前约定（通常是“左结合”）。
这种“一种输入、多种语法树”的情况，叫歧义，是语法分析要特别处理的麻烦。它也是后面一节的重点。
那么，用什么工具来精确描述程序语言的语法呢？下一章引入上下文无关文法。
思考题 1
语法分析相比词法分析，多解决了什么问题？
思考题 2
为什么同一串词法单元，可能有不同的语法结构？
小结
知识点
- 语法分析把词序列组织成语法结构
- 它要判断合法性并给出结构
- 语法树表示词之间的层级关系
- 同一串词可能存在多种结构（歧义）
参考资料
- Wikipedia(zh)：语法分析：把词法单元组织为语法结构
- Wikipedia(zh)：抽象语法树：程序语法结构的树形表示
思考题答案（仅供参考）
思考题 1
词法分析只把字符切成词，产出的是平铺序列；语法分析在此之上判断这串词是否符合文法，并给出它们的层级结构（语法树），从而揭示谁包含谁、运算如何组织。
思考题 2
因为文法规则可能允许多种组合方式。例如 1 - 2 - 3 既可以结合成 (1-2)-3，也可以结合成 1-(2-3)。若语言没有明确规定优先级或结合性，就会出现多种结构，即歧义。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪