在当前非终结符下 根据当下的终结符选择当前非终结符的某个展开式进行展开
自左向右
根据下一个token决定选用哪一个文法
存在的问题
左递归,会存在无限循环问题
P→Pa|b (b 不以P开头)
转为
P→bP`
P`→aP`|空还存在间接左递归问题,但是可以通过代入变成直接左递归. 下面算法直接一步到位,消除了环状递归 and 左递归 and 间接左递归
最好是让G排在最后
每一个式子都是只引用排序比自己靠后的, 所以没有环状递归.
❓
式子里包含自己的话就会死循环
例子
回溯问题-此路不通
如果回溯的话会增大实现难度.
first集
非终结符的所有首个终结符的集合
用递归求, 如果A→Bc 那么first(A)包含first(B)
follow集
可以跟在这个符号后的终结符集合
算法
select集
first集和follow集就是为了计算select集
当A→空 时,select(A) = follow(A) ;
当A→Bc 时,select(A) = first(B) ;
预测分析表
•
select集要不相交才行. 提取公因子
最后用select集构建预测分析表
评论区