一、上下文无关文法
1.定义
上下文无关文法是这样一个四元组（VT , VN , S, P）
VT：终结符集合，非空有限集合，记号名是其同义词
VN：非终结符集合，非空有限集合且VT∩VN=Φ
S：开始符号
P：产生式集合，形如A -> a，A∈VN，a∈(VN∪VT)*
其中，终结符可以理解为词法单元，即是符号的最终形式，非终结符就是匹配终结符过程中引入的中间量，
例({
id, +, *, –, (, )}, {
expr,op}, expr,P )
以下符号通常表示终结符：
- 字母表中前面的小写字母，如a,b,c
- 黑体串,如id或while
- 数字 0,1,…,9
- 标点符号，如括号，逗号等
- 运算符号，如+,-等
以下符号通常表示非终结符
- 字母表中前面的大写字母，如A,B,C
- 字母S, 通常它表示开始符号
- 小写字母的名字，如expr和stmt
2.上下文无关文法与正规式比较
上下文无关文法：
E -> E A E | (E ) | –E | id
A -> + | *
正规式：
letter ->[A-Za-z]
digit ->[0-9]
id ->letter(letter|digit)*
- 正规式来定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复
- 正规式不能用于描述配对或嵌套的结构，例如配对括号串的集合
因此通过引入上下文无关文法来进行语法分析
3.推导
推导：用于确定符合文法规则所规定的结构的串的集合(用来确定一个语言)
推导从一个结构名字开始，并在得到记号串作为结束
把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替
例：E -> E + E | E * E | (E ) | – E | id
E —》 –E —》 –(E) —》 –(E + E) —》-(id + E)—》 –(id + id)
上下文无关语言：由一个文法推导出来的结果
句型：包含非终结符的推导结果
句子：全部为终结符的推导结果-》即最终结果
推导就是一个把上下文无关文法转化为句子的过程
在推到的过程中涉及到同级别表达式的替换，因此按推到顺序可以分为最左推导和最右推导，顾名思义：
最左推导：推导过程中始终最先代换最左侧的文法
最右推导：推导过程中始终最先代换最右侧的文法
举个例子：
可以看出最左推导和最右推导产生的分析树结构是不一样的，为什么会产生这种情况，就是因为文法的二义性
4.二义性
文法的二义性，是指对于符合文法规则的同一个句子，存在两种可能的分析树
产生原因
类似+ 和*这种不同的优先级在文法中没有得到体现
消除方法
用层次的观点看待表达式
根据运算符优先级不同，引入新的非终结符
比如将上式产生二义性的文法引入一个中间量
E ->E + T | T
T -> T * F | F
F -> id | (E)
5.分析树
上文中多次涉及分析树，其实分析树就是根据推导过程建立的树形结构，他的所有叶子节点都是终结符，所有非叶子结点都是非终结符，根节点是文法的开始符号
6.上下文无关文法的优缺点
优点：
- 给出了精确的，易于理解的文法说明
- 自动产生高效的分析器
- 可以给语言定义出层次结构
- 以文法为基础的语言实现便于语言的修改
缺点：
文法只能描述编程的部分语法
二、NFA->上下文无关文法
- 确定终结符集合
- 为每个状态引入一个非终结符Ai
- 如果状态i有一个a转换到状态j，引入产生式Ai->aAj，如果i是接受状态，则引入Ai->e（空串）
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/233278.html原文链接：https://javaforall.net
