Mar*_*rko 20 parsing context-free-grammar ll-grammar
任何人都可以向我解释如何在LL(1)语法中使用FIRST和FOLLOW？我知道它们用于语法表构造,但我不明白如何.
tem*_*def 40
在LL(1)解析器中,解析器通过维护最初接种到起始符号的工作空间,然后是字符串结束标记(通常表示为$)来工作.在每个步骤中,它执行以下操作之一:
预测步骤是FIRST和FOLLOW出现的地方.解析器需要能够完全基于当前的非终结符和输入的下一个标记来猜测要使用的生产.问题是如何做到这一点.
假设当前的非终结符号为A,输入的下一个标记为t.如果你知道A的制作,你会选择哪一个？有一个简单的例子要考虑:如果有一个形式A→tω的产生,其中ω是一些任意的字符串,那么你应该选择那个产量,因为你看作输入的t将匹配前面的t生产.
还有一些复杂的案例需要考虑.假设你有A→Bω形式的产生,其中B是非终结符,ω是某个字符串.在什么情况下你想猜这个产品？好吧,如果你知道下一个终端符号是,你不会想要猜测这个生产,除非你知道B可以扩展到以终端t开头的字符串(还有另一个我们将要讨论的情况)第二).这是FIRST集合的用武之地.在没有ε产生的语法中,某些非终结符号的集合FIRST(X)是可能出现在从X派生的某个字符串的开头的所有终端的集合.如果你有形式A→Bω,你看到非终结t,你猜想在t∈FIRST(B)时精确地使用该生产; 也就是说,B可以导出一些以t开头的字符串.如果B没有得到以t开头的任何东西,那么没有理由选择它,如果B确实得到以t开头的东西,你想做出这个选择,这样你最终可以匹配它.
当ε产品推出时,事情变得有点棘手.现在,让我们假设你有一个形式A→BCω,其中B和C是非终结符,ω是一个字符串.我们还假设下一个输入标记是t.如果t∈FIRST(B),那么我们就选择这种生产,如上所述.但是,如果t∉FIRST(B)会发生什么？如果语法中有ε产生,如果B可以导出ε和t∈FIRST(C),我们可能仍然想要选择这个产生.为什么是这样？如果发生这种情况,则意味着我们可能通过产生BCω来匹配t,然后从B产生ε,留下Cω与t匹配.这是我们可能必须"浏览"非终结者的一个背景.幸运的是,这是由FIRST集处理的.如果非终结X可以产生ε,那么ε∈FIRST(X).因此,我们可以使用FIRST集来检查我们是否需要通过查看ε∈FIRST(X)来"查看"非终结符.
到目前为止,我们还没有谈到FOLLOW集.他们来自哪里？好吧,假设我们正在处理非终结符号A,我们看到终端t,但是A的生成都没有实际消耗t.那我们做什么？事实证明,仍有一种方法可以让我们吃掉它.请记住LL(1)解析器通过维护带有字符串的工作空间来工作.我们所看到的可能根本不应该与当前的非终结符号A匹配,而是我们应该有A产生ε然后让工作区中的一些后来的非终结符合t.这是FOLLOW集合的来源.非终结符号的FOLLOW集合,表示为FOLLOW(X),是在某些派生中可以紧接在X之后出现的所有终端符号的集合.当选择为A选择哪个生产时,我们添加一个最终规则 - 如果终端符号t在A的FOLLOW集合中,我们选择一些最终将产生ε的生产.这样,A将"消失",我们可以将t与A非终结后出现的某些角色进行匹配.
这不是对LL(1)解析的完整介绍,但我希望它能帮助您了解我们为什么需要FIRST和FOLLOW集合.有关更多信息,请阅读一本关于解析的书(我推荐Parsing Techniques: Grune和Jacobs的实用指南)或参加编译器课程.作为一个完全无耻的插件,我在2012-2013夏季教授编译器课程,所有的演讲幻灯片都可在线获取.
希望这可以帮助!