编译原理学习笔记2（语法分析介绍）

3 语法分析

在学习语法分析之前，先梳理一下人类让机器理解语言的大致脉络（自己画的）：

3.1 介绍

词法分析中的单词是一种由字符组成的线性结构，而语法分析中的句子的语法结构是一种非线性结构，反映这种结构的最好方法是树，常用的有分析树和语法树。分析语法结构的基本方法有：自上而下分析方法（对应预测分析器）和自下而上分析方法（对应移进-规约分析器），将在后文进行介绍。
语法分析也有双重含义：

1）规定句子形成的规则，也被称为语法规则；
2）根据语法规则识别记号流中的语言结构，也被称为语法分析。

主要工作为：

1）根据词法分析器提供的记号流，为语法正确的输入构造分析树/语法树；
2）检查输入中的语法错误，并调用出错处理器进行处理。

乔姆斯基（Chomsky）把文法分为四种类型：0型（短语文法，对应图灵机），1型（上下文有关文法，对应线性界线自动机），2型（上下文无关文法，对应下推自动机）和3型（正规文法，对应有限自动机），i型文法比i+1型文法能力强。一般，文法指上下文无关文法。

3.2 上下文无关文法

CFG（上下文无关文法）是一个四元组G=（N，T，P，S），分别对应非终结符集合，终结符集合，产生式集合，文法开始符号。
CFG产生语言的基本方法是推导，即从开始符号开始，反复使用产生式，直到得到一个终结符序列。
每次替换最左边的推导叫最左推导，同理有最右推导。
推导的过程可以用分析树来表示，最后生成的分析树根部为开始符号，所有叶子连起来就是推导出的句子。
在正规式中，无穷可枚举是通过星运算来表示的，而CFG中没有星运算，但是可以通过产生式的递归推导来产生无穷的串。
正规式所描述的语言均可以使用CFG描述，但反之不一定。比如：

L(G) = {aⁿbⁿ| n≥1}，用CFG可以使用产生式A->aAb|ab描述出来，但是正规文法无法描述该语言。

杂记

上下文有关/无关里的上下文：个人理解，主要是为了描述在程序设计语言中所出现的一致性关系，前文出现的东西，后面有与它对应的东西。比如实参与形参（aⁿb^mcⁿd^m，其中aⁿb^m为形参表，cⁿd^m为实参表），变量的声明和引用（ωcω），并且一致性关系的双方中间需要隔一点内容，比如a^mb^mc^m算上下文有关，但a^mb^mcⁿ就是上下文无关。