语法分析
-
简介
语法分析简介.png -
上下文无关语法
-
形式化(只是个例子)
S -> N V N N -> s | t | g | w V -> e | d 非终结符:{S,N,V} 终结符:{s,t,g,w,e,d} 开始符号:{S} -
严格的数学定义
G = {T,N,P,S} T为终结符集合, N为非终结符集合, P是一组产生式规则, S是唯一的开始符号; -
BNF范式
- <E>:非终结符
- 下划线:终结符
分析树
二义性文法
-
-
自顶向下分析(逐个尝试)
-
自顶向下
tokens[]//输入的字符串 i=0 stack=[s]//栈 while(stack!=[]){ if(stack[top] is a terminal t){ if(t==tokens[i++]){ pop() }else{ backtrack() } }else if(stack[top] is a nonterminal T){ pop() push(the next right hand side of T) } } -
递归下降分析算法
-
递归实现读取
parse_S(){ parse_N(); parse_V(); parse_N(); } parse_N(){ token = tokens[i++]; if(token==s||token==t||token==g||token==w){ return//识别了就直接return并且上面已经i++了 } error(); } parse_V(){} -
递归实现识别算术运算符
Recursive descent algorithm.pngparse_E(){ parse_T(); token = tokens[i++]; while (token==+){ parse_T(); token = tokens[i++]; } } parse_T(){ parse_F(); token = tokens[i++]; while(token==*){ parse_F(); token = tokens[i++]; } }
-
-
LL(1)分析算法
从左(L)向右读入程序,最左(L)推导,采用一个(1)前看符号
- LL(1)分析表
- 根据前看符号来判断,就是tokens中现在指针指向的元素.
- 分析表.png
- 上下文无关文法.png
-
栈执行顺序图 计算1.JPG
- LL(1)表中的冲突
- LL(1)分析表中一个非终结符对应了两种
- NULLABLE表的构建:
NULLABLE.png - FIRST集合的完整计算公式
FIRST集合计算公式.png
- LL(1)分析表
-
-
自底向上算法
- LR分析算法
