1. 语法分析位置
通过语法分析器输入tokens,语法分析器(parser)生成一棵分析树
2. 上下文无关文法
CFG(Context-Free Grammars)是编程语言语法结构的规范,使用类似于正则表达式的词汇结构规范
定义
,非终结符的有限非空集合
, 终结符的有限非空集合
, 开始符号
, 产生式
组成
| non-terminals | 非终态符号,某个语法变量,代表一组或一类结构 | | —- | —- | | terminals | 终态符号,即某个词法单元名,如
产生式的递归
production分为左右递归,区别在于:对于产生式A,左(右)递归时右部中定义A的规则中non-terminal作为第一个(最后一个)symbol出现
推导
产生式作为一组规则(合法的tokens),能通过其推出串(句子),过程即为”推导”(derivations)
最左/右推导
- leftmost:替换每个句型的最左non-terminal
- rightmost:替换每个句型的最右non-terminal
分析树
分析树作为推导图形化,忽略了non-terminals应用顺序,因此推导和分析树之前存在一对多关系;但是parsing tree和最左/最右推导存在唯一对应关系
二义性
给定某种语言/句子,求其文法,此时可能产生二义性问题,比如2+56,可以理解为(2+5)6也可以是2+(56).给出定义:*一个文法可生成多棵分析树时,该文法是二义的
⭐证明
一个句子有多个最左**(最右)推导/可画出多棵parsing tree**
二义性解决
在构造文法时必须要避免二义性,通常从优先级(preference)和结合性(associativity)入手
优先级:让优先级低的运算符放在离开始符号近的production中(即用更多步骤得到更高优先级的符号)
结合性:
- 左递归production中的运算符是左结合的(语言从左向右执行)
- 右递归production中的运算符是右结合的
3. ⭐构造无二义性的CFG
总结:
- 由①任何语言,先判断优先级,n个优先级需要n+1个非终符号(结果n+1个式子)
- 由②,先判断语言的因子factor产生式->”语言的最小运算元素num,id|[当语言可以使用括号时(exp)]”
- 由③④,从高优先级开始构造,最高优先级的production->”使用rule|factor”
- 由④,依次向下,其余优先级production->”使用rule|高一级production”
- 直到抵达最低优先级,即开始符号exp的production
- 最终生成按优先级从低到高最后写factor
以上每一步的production还应考虑结合性进行转化
若有收获，就点个赞吧
0 人点赞
