词法分析与语法分析区别
- 词法分析：字母是元素，组成字符串，记号的集合，线性结构
- 语法分析：记号是元素，组成句子，句子的集合，树结构
词法：构词规则和词法分析（识别输入序列）
语法：语法规则（上下文无关文法）和语法分析（下推自动机，自上而下，自下而上分析等）
错误处理方面的区别：
- 语法错误：常见，方便诊断。
- 语义错误：较难诊断。
上下文无关文法（CFG）
CFG是一个四元组G =（N，T，P，S），其中
- N是非终结符（Nonterminals）的有限集合；
- T是终结符（Terminals）的有限集合，且N∩T=Φ；
- P是产生式（Productions）的有限集合，形如：A→α，其中A∈N（左部），α∈(N∪T)*（右部），若α=ε，则称A→ε为空产生式（也可以记为A →）；
- S是非终结符，称为文法的开始符号（Start symbol）。
产生式集表示
- 文法开始符号S是第一个产生式的左部；
- N是可以出现在产生式左边符号的记号集合；
- T是绝不出现在产生式左边符号的记号集合；
产生式表示也称为巴克斯范式，→用::=表示
产生式缩写
左部非终结符相同可合并，右部是所有原来右部的或运算（并），用|连接，注意，右部的每一个候选项具有平等的权利。
产生语言的基本方式-推导
从开始符号开始，反复使用产生式，得到终结符序列。
直接推导记作：αAβ=>αγβ。零步或多步推导，记为：α1=*>αn，其中α1=αn的情况为零步推导。若α1≠αn，即推导过程中至少使用一次产生式，则称此过程为至少一步推导，记为：α1=+>αn。
上下文无关语言
由CFG G所产生的语言L(G)被定义为:
L(G) = { ω┃S=+>ω and ω∈T* }，
L(G)称为上下文无关语言(Context FreeLanguage, CFL)，
ω称为句子。
若S=*>α，α∈(N∪T)*，则称α为G的一个句型
最左推导产生左句型，最右推导产生右句型，最右推导也称为规范推导。
分析树
根由开始符号标记，叶子由终结符，非终结符，或ε标记，内部节点由一个非终结符标记。父节点A->孩子节点XYZ...是一个产生式。若A→ε，则标记为A的结点可以仅有一个标记为ε的孩子。
叶子从左到右构成句型，若仅由终结符标记则构成一个句子。
最左推导与最右推导的分析树可能不同。
语法树
根与内部节点由表达式中的操作符标记；叶子由表达式中的操作数标记；用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中。
分析树与语法树的区别
- 分析树的内部节点是非终结符；
- 语法树的内部节点是操作符（运算符）；
- 或者说语法树中省略了反映分析过程的非终结符
二义性及其消除
二义性
一个句子可能对应多颗分析树，则该文法就是二义性的。
文法二义不一定所产生的语言二义。
消除二义性
- 改写。优先级高的离开始符号远，递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。
- 规定符号的优先级和结合性。
正规式到CFG的转换
正规式描述的语言结构均可用CFG描述，反之不一定。（CFG树形结构，正规式线性结构，简单的可以用复杂的表示）
从正规式到CFG的转换：
- 构造NFA，用a-->b的方式描述NFA.
- 按照经验描述。
