将无上下文语法转换为LL(1)语法 [英] Converting a context-free grammar into a LL(1) grammar

查看:195
本文介绍了将无上下文语法转换为LL(1)语法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

首先,我检查了类似的问题,但没有一个提供我想要的信息.

First off, I have checked similar questions and none has quite the information I seek.

我想知道,鉴于上下文无关的语法,是否可以:

I want to know if, given a context-free grammar, it is possible to:

  • 知道是否存在等效的LL(1)语法.从某种意义上讲,它应该产生相同的语言.
  • 将上下文无关的语法转换为等效的LL(1)语法(如果存在).如果存在等效的LL(1)语法,则转换应该成功.如果等效项不存在则不终止也可以.

如果对这些问题的回答是是",那么是否可以在某处找到这种算法或工具?我自己的研究没有成果.

If the answer to those questions are yes, are such algorithms or tools available somewhere ? My own researches have been fruitless.

另一个答案提到《龙书》有一个消除左递归和左因子分解上下文无关文法的算法.我可以访问该书并进行检查,但是对于语法是否保证为LL(1)尚不清楚.对上下文无关文法施加的限制(没有零产生和没有循环)对我来说是可以接受的.

Another answer mentions that the Dragon Book has an algorithms to eliminate left recursion and to left factor a context-free grammar. I have access to the book and checked it but it is unclear to me if the grammar is guaranteed to be LL(1). The restriction imposed on the context-free grammar (no null production and no cycle) are agreeable to me.

推荐答案

我从大学编译器课程中学习,我记得LL(1)语法是上下文无关的语法,但是上下文无关的语法比LL(1)大得多.没有检查和从无上下文关联(可以转换为LL(1))再转换为LL(1)的通用算法(意味着不是NP困难的).

From university compiler courses I took I remember that LL(1) grammar is context free grammar, but context free grammar is much bigger than LL(1). There is no general algorithm (meaning not NP hard) to check and convert from context-free (that can be transformed to LL(1)) to LL(1).

要集成函数时,应用诸如删除左递归,消除第一跟进冲突,左因数分解之类的技巧类似于数学变换.艺术.这些变换通常彼此相反.

Applying the bag of tricks like removing left recursion, removing first-follow conflict, left-factoring, etc. are similar to mathematical transformation when you want to integrate a function... You need experience that is sometimes very close to an art. The transformations are often inverse of each other.

为什么现在经常将LR类型语法用于生成的解析器的一个原因是,它们比LL(1)涵盖了更广泛的上下文无关语法.

One reason why LR type grammars are being used now a lot for generated parsers is that they cover much wider spectrum of context free grammars than LL(1).

顺便说一句.例如C语法可以表示为LL(1),但是C#不能(例如,想到lambda函数x -> x + 1时,您无法确定是看到lambda的参数还是已知变量).

Btw. e.g. C grammar can be expressed as LL(1), but C# cannot (e.g. lambda function x -> x + 1 comes to mind, where you cannot decide if you are seeing a parameter of lambda or a known variable).

这篇关于将无上下文语法转换为LL(1)语法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆