File tree Expand file tree Collapse file tree 1 file changed +5
-5
lines changed Expand file tree Collapse file tree 1 file changed +5
-5
lines changed Original file line number Diff line number Diff line change 21
21
&emsp ;&emsp ;&emsp ; ③获取js文法:根据js语言特点得到形式化定义文法G。
22
22
<br />
23
23
&emsp ;&emsp ;&emsp ; ④文法G优化:先提取G产生式左公共因子,再消除左递归,这样就有可能变为LL(1)文法。然后要分别写出改写后文法的FIRST集、FOLLOW集、SELECT集,如果相同左部的SELECT集的交集不为空集,则为LL(1)文法。
24
- ⑤即使部分文法不能完全满足LL(1),也没关系,我们可以通过特例特殊处理的办法使得整体文法兼容到LL(1)预测分析算法。这步通常可以满足所有编程语言,还不好处理的话就只能采用自底向上算法了。(《 为什么所有的教科书中都不赞成手写自底向上的语法分析器? - 冯东的回答 - 知乎 https ://www.zhihu.com/question/21475266/answer/18346898》)
24
+ ⑤即使部分文法不能完全满足LL(1),也没关系,我们可以通过特例特殊处理的办法使得整体文法兼容到LL(1)预测分析算法。这步通常可以满足所有编程语言,还不好处理的话就只能采用自底向上算法了。[ 为什么所有的教科书中都不赞成手写自底向上的语法分析器? - 冯东的回答 - 知乎 ] ( https ://www.zhihu.com/question/21475266/answer/18346898)
25
25
<br /><br /><br />
26
26
27
27
158
158
N → s | t | g | w
159
159
V → e | d
160
160
```
161
- ~ &emsp ; 一个从编程语言生成文法的实例:《 如何写出文法》 https://www.zhihu.com/question/51341918
161
+ ~ &emsp ; 一个从编程语言生成文法的实例:[ 如何写出文法] ( https://www.zhihu.com/question/51341918 )
162
162
* CFG分析树:
163
163
```
164
164
设计文法G(简化版本算术表达式文法):
208
208
</br >
209
209
~ &emsp ; 最右推导:在自顶向下最右推导中,总是选择每个句型的最右终结符进行替换。最左规约是最右推导自底向上的逆过程
210
210
* 分析树采用最左或者最右推导,推出的结果是唯一的。因为在推导的每一步,当前句型中的最左或最右非终结符都是唯一的
211
- * (重要)由于分析都在自左向右的扫描tokens,所以自顶向下分析采用最左推导方式:( https://www.bilibili.com/video/BV1zW411t7YE?p=19,07:45的时候详细展示了推导过程)
211
+ * (重要)由于分析都在自左向右的扫描tokens,所以自顶向下分析采用最左推导方式:[ 编译原理·哈尔滨工业大学·07:45的时候详细展示了推导过程 ] ( https://www.bilibili.com/video/BV1zW411t7YE?p=19 )
212
212
</br >
213
213
~ &emsp ; 总是选择每个句型的“最左非终结符”进行替换
214
214
</br >
234
234
a b c
235
235
解析:初始时输入指针指向a,从文法S开始推导,S的两个候选式都是以输入流a开始,所以不能确定选择哪个,所以产生回溯。这种回溯可以通过引入其他非终结符Term,或者也叫通过提取公因子方式解决:经过反复提取左因子,就能够把每个非终结符的所有候选首符集变成为两两不相交。
236
236
```
237
- ~ &emsp ; 回溯实例2:https://zhuanlan.zhihu.com/p/67083281
237
+ ~ &emsp ; 回溯实例2: https://zhuanlan.zhihu.com/p/67083281
238
238
* 预测分析(Predictive Parsing):
239
239
</br >
240
240
~ &emsp ; 预测分析不需要回溯,是一种确定的自顶向下分析方法。
276
276
~ &emsp ; LR分析算法过程无回溯,是最高效的分析算法之一,所以其自动化生成算法可以被工程应用。
277
277
</br >
278
278
~ &emsp ; LR分析算法可尽早地检测到语法错误。
279
- * LL文法比LR文法的优势:( https://www.zhihu.com/question/21475266/answer/18346898)
279
+ * LL文法比LR文法的优势:https://www.zhihu.com/question/21475266/answer/18346898
280
280
</br >
281
281
&emsp ;&emsp ; LR文法解析通常采用自底向上语法分析算法,而自底向上语法分析算法的实现较复杂,可读性差,所以很多教材推荐采用工具生成(绝大多数是 bison/yacc)。而手工实现LL文法的自顶向下parse工程上更适合。
282
282
</br >
You can’t perform that action at this time.
0 commit comments