欧亚达网站是哪家公司做的,磁力蜘蛛搜索引擎,展厅设计包括哪些内容,网站源码下载免费源码目录 引言上下文无关文法 CFG: Context-Free Grammar定义推导方法最左推导和最右推导 分析树分析树-抽象语法树常见的上下文无关文法文法设计二义性文法扩展巴科斯范式#xff1a;EBNF extended Backus Normal Form 文法和语言分类相关术语直接推导推导*推导句型、句子、语… 目录 引言上下文无关文法 CFG: Context-Free Grammar定义推导方法最左推导和最右推导 分析树分析树-抽象语法树常见的上下文无关文法文法设计二义性文法扩展巴科斯范式EBNF extended Backus Normal Form 文法和语言分类相关术语直接推导推导*推导句型、句子、语言短语、简单短语、句柄 正则文法DFA-正则文法正则文法-DFADFA-正则表达式正则文法-正则表达式正则表达式-正则文法 自顶向下分析方法LL分析算法 top-down parsing回溯分析方法backtracking parser预测分析方法 predictive paeser递归下降分析 recursive-descent parsingLL(1)分析法 ll(1) parsing (重点First集合Follow集合 (重点 自底向上分析方法LR分析算法bottom-up parsing 引言
语法分析器的作用token序列-分析树、抽象语法树
语法错误可能有
关键字、标识符拼写错误如intege语法结构出错少分号begin/end不匹配静态语义错误类型不一致、参数不匹配如需要传入double却传入了char动态语义错误无穷递归这就是为什么有的编译器会报错whille(t){}里没有t–即使你在块里写了它也找不到因为它只看一开始有没有很傻、0作除数
处理目标
正确报告错误以及地点有一些明明是x行错误却报y行错误迅速恢复要么一直找直到找到想要的记号这样比较愚蠢要么替换纠正容易改不对引发更多报错不影响源程序的分析速度
词法分析可以合并到文法当中
上下文无关文法 CFG: Context-Free Grammar
文法是对语言结构的定义和描述。即从形式上用于表述和规定语言的结构称为“文法”。如“草吃羊”在文法上正确但语义不正确。
定义
GT,N,P,S T 是终极符号集合可以理解为token一般用小写、黑体表示 N是非终结符号集合一般用大写、小写斜体表示 P是产生式或文法规则A-a集合其中A是非终结符a是(TUN)*如句子-主语宾语 S是唯一的开始符号是非终结符
另外小写希腊字符表示文法符号串可为空
暂时没有自动生成上下文无关文法的工具必须手动写
推导方法
给定文法G从G的开始符号S开始推导不断用相应规则的右部来替代规则的左部每次仅用一条规则去推导直到所有的非终结符都被终结符号替代为止。 依据上述过程最终的串称为句子所有句子的集合称为语言。定义如下 L ( G ) { s ∣ S ∗ s } L(G)\{s|S*s\} L(G){s∣S∗s}其中推出符号*表示经过0或多步推导出。
最左推导和最右推导
有若干语法成分同时存在时总是从最左的语法成分进行推导这称之为最左推导。同理可以定义最右推导 例 文法
exp-exp op exp|(exp)|**number**
op-|-|\*需要分析的字符串34-3*42 推导过程
expexp op exp
exp op number
exp * number(exp)*number
(exp op exp)*number
(exp op number)*number
(exp - number) * number
(number - number ) * number上例是最右推导最左推导如下
(1) exp exp op exp [exp - exp op exp]
(2) (exp) op exp [exp - (exp)]
(3) (exp op exp) op exp [exp - exp op exp]
(4) (number op exp) op exp [exp - number]
(5) (number - exp) op exp [ op - - ]
(6) (number - number) op exp [exp - number]
(7) (number - number) * exp [ op - *]
(8) (number - number) * number [exp - number]上下文无关文法举例
文法GE-(E)|a 文法定义的语言是L(G){a,(a),((a)),…}{ ( n a ) n ∣ (^na)^n| (na)n∣n是0的整数}G:E-Ea|a文法定义的语言是L(G){a,aa,aaa,…}正则式a文法是G:A-Aa|a或者A-aA|a语言是L(G){ a n a^n ann是1的整数}正则式a*文法是G:A-Aa|ε或者A-aA|ε语言是L(G){ a n a^n ann是0的整数}文法G:E-(E) 语言是L(G){}没有终结符没有句子无限递归
分析树
以上例为例 看序号可知是最左推导与前序编号对应 下面是最右推导与后序遍历对应
①父节点和子结点之间构成了一条文法规则 ②叶节点都是终结符号内部结点都是非终结符号
每个分析树只有唯一的一个最左推导和一个最右推导
分析树-抽象语法树 分析树复杂但信息丰富而抽象语法树简洁、抽象用于语义分析
常见的上下文无关文法
算数表达式
exp-exp op exp|(exp)|**number**
op-|-|\*if-else 下面这个文法有重叠的部分比较低效
G: statement - if-stmt | other
if-stmt - if ( exp ) statement |if ( exp ) statement else statement
exp - 0 | 1下面这个文法是有歧义的文法
G: statement - if-stmt | other
if-stmt - if ( exp ) statement else-part
else-part - else statement | ε
exp - 0 | 1括号匹配文法
G: A -(A)A|ε带分号的文法 这个文法是错的他的缺点是最后一个语句没有结束的分号
stmt-sequence - stmt ; stmt-sequence | stmt
stmt - s下面这个文法可以但是会推导出空语句:L(G’) {ε, s;, s;s;, s;s;s;,…}
stmt-sequence - stmt ; stmt-sequence | stmt | ε
stmt - s下面这个也是
stmt-sequence - stmt-other1 stmt-other2
stmt-other1 - stmt | ε
stmt-other2 - ;stmt stmt-other2 | ;
stmt - s文法设计
二义性文法
可生成两个不同分析树的串的文法叫二义性文法。 如34-3*42的分析树与语法树可以有两种。 算术表达式文法存在二义性的根源是什么有2条规则都能往下推导没有考虑优先级。
消除二义性的方法 1.不修改文法指定正确的分析树只需手动修改生成的代码LL分析表有冲突时选择其中一条 2.修改文法会改得很乱
1.算术表达式修改文法确定乘法优先级于加法;
exp - exp addop exp | term
addop - | -
term - term mulop term| factor
mulop - *
factor - (exp) | number在此基础上确定乘法和加法都是左结合的
exp - exp addop term | term
addop - | -
term - term mulop factor | factor
mulop - *
factor - (exp) | number下面这个文法的缺陷是输入者必须输入带括号的表达式
exp factor op factor | factor
factor (exp) | number
op | – | *2.if-else悬挂的else问题在这里插入代码片 最近嵌套规则用于解决悬挂else问题
statement matched-stmt | unmatched-stmt
matched-stmt if ( exp ) matched-stmt else matched-stmt | other
unmatched-stmt if ( exp ) statement | if ( exp ) matched-stmt else unmatched-stmt
exp 0 | 1下面的文法是强制if加上end
if-stmt - if condition then statement-sequence end if |if condition then statement-sequence else statement-sequence end if3.无关紧要的二义性文法分号结尾的语句
stmt-sequence - stmt-sequence ; stmt-sequence | stmt
stmt - s扩展巴科斯范式EBNF extended Backus Normal Form
{}表示重复
用[]表示可选比如
G: statement if-stmt | other
if-stmt if ( exp ) statement [ else statement ]
exp 0 | 1文法和语言分类
0型、1型、2型、3型乔姆斯基层次
-产生式左部范围右部范围左部右部备注0型u-v(TUN)(TUN)*10可计算枚举语言短语结构文法1型xUy-xuy(TUN)(TUN)*10上下文相关文法2型U-vN(TUN)*10上下文无关文法3型U-t,U-WtNTUN12正则文法、线性文法
越往高级限制越多高级的语言符合低级
(左线性) PU - t 或 U - Wt 其中 U、W∈N t∈T (右线性) PU - t 或 U - tW 其中 U、W∈N t∈T 这一分类的研究意义在于模型的可解释性但是它的描述能力较弱
相关术语
直接推导 推导 等于说是通过一步或多步推导出来的
*推导 通过0步或多步推导
句型、句子、语言
文法G (T, N, P, S)S * a 如果a是(TUN)*那么a是句型 存在非终结符号。即分析树的剖面 如果a是T*那么a是句子全部是终结符号也就是叶子节点句子属于句型 文法G产生的语言是L(G[S]) {a | S * a a ∈ T* }
短语、简单短语、句柄
G (T, N, P, S)w xuy ∈ (TUN)* 为文法的句型 若S xUy 且 U u则u是句型w相对于U的短语子树 若S xUy, 且 U u则u是句型w相对于U 的简单短语; U是非终结符u是一步或多步的TUN,xy都是0步或多步的TUN 任一句型的最左简单短语称为该句型的句柄。
例子 黄色是剖面句型 可以发现这种话的说法就是“u是句型xx相对于U的短语”其中句型是固定的,因为这是题里给的u是黄色的结点U是他们规约以后蓝色的结点 简单短语也就是一步可以得出的最左的简单短语是句柄
正则文法 DFA-正则文法 例子 普通的转移直接把吃进的字符和到达的状态连起来当右部出发点当左部可接收的状态再加一条可以推出epsilon
正则文法-DFA 先按反过程画出来DFA画完所有的以后加一个终态Z把那些可以推出epsilon的状态都指向Z把那些直接推出终结符的语句也指向Z
DFA-正则表达式 将词法分析的流程反向做一遍 r ( a ∣ b ) ∗ ( a a ∣ b b ) ( a ∣ b ) ∗ r (a|b)*(aa|bb)(a|b)* r(a∣b)∗(aa∣bb)(a∣b)∗
正则文法-正则表达式 递归即闭包
正则表达式-正则文法
上表反过来
自顶向下分析方法LL分析算法 top-down parsing
从文法G的开始符号S开始推导得出句子t遍历所有t如果t给定的句子s那么s可以由G推导出来。
回溯分析方法backtracking parser
思想就是往下推导如果不匹配就回溯效率非常低不聪明。没人用。
tokens[ ]; /* 词法分析得到的单词列表 */
int i 0;
stack [S]; /* 栈内放文法的开始符号 */
while ( stack ! [] )if (stack[top] 是终结符号 t )if ( t tokens[i] ) { i; pop(); }else { backtrack( ) }else if (stack[top] 非终结符号 T )pop( ); push( 关于非终结符号T的下一条规则的右部 )压栈的时候是从右往左压一旦栈顶是终结符就去匹配不匹配就回溯匹配就消掉
预测分析方法 predictive paeser
递归下降分析 recursive-descent parsing
LL(1)分析法 ll(1) parsing (重点
First集合Follow集合 (重点
自底向上分析方法LR分析算法bottom-up parsing
