标签: context-free-grammar

任何人都可以向我解释如何在LL(1)语法中使用FIRST和FOLLOW？我知道它们用于语法表构造,但我不明白如何.

我无法理解如何计算LR(1)-items的前瞻.

让我们说我有这个语法:

S -> AB
A -> aAb | a
B -> d

LR(1)-item是具有前瞻的LR(0)项.所以我们将为状态0得到以下LR(0)-item:

S -> .AB , {lookahead} 
A -> .aAb,  {lookahead} 
A -> .a,  {lookahead}

州:1

A ->  a.Ab, {lookahead} 
A ->  a. ,{lookahead} 
A -> .aAb ,{lookahead} 
A ->.a ,{lookahead}

有人可以解释如何计算前瞻吗？一般方法是什么？

先感谢您

我正在研究C的解析器.我正在尝试找到C的所有无上下文派生的列表.理想情况下,它将在BNF或类似的情况下.我确信这样的事情就在那里,但谷歌搜索并没有给我太多.

阅读现有解析器/编译器的源代码已被证明比有用的更令人困惑,因为我发现的大多数都比我正在构建的更加雄心勃勃和复杂.

我正在尝试学习与编程语言相关的Chomsky Hierarchy的某些方面,我仍然需要阅读Dragon Book.

我读过大多数编程语言都可以解析为无上下文语法(CFG).就计算能力而言,它等于下推非确定性自动机之一.我对吗？

如果这是真的,那么CFG怎么能保持一个不受限制的语法(UG),这是完整的？我问,因为即使编程语言由CFG描述,它们实际上也用于描述图灵机,所以通过UG.

我认为这是因为至少有两个不同的计算级别,第一个,即CFG的解析侧重于与语言结构(表示？)相关的语法,而另一个侧重于语义(意义,解释)数据本身？)与编程语言的功能有关,这是完整的.再次,这些假设是对的吗？

我正在努力学习如何制作编译器.为了做到这一点,我读了很多关于无上下文的语言.但是有一些我自己无法得到的东西.

因为它是我的第一个编译器,所以有一些我不知道的实践.我的问题是在构建一个解析器生成器,而不是编译器和lexer.有些问题可能很明显..

我的读物包括:自下而上的解析,自上而下的解析,正式的语法.显示的图片来自:Miscellanous Parsing.全部来自斯坦福CS143级.

以下是要点:

0)(模糊/明确)和(左递归/右递归)如何影响一种算法或另一种算法的需求？还有其他方法来限定语法吗？

1)模糊语法是具有多个解析树的语法.但是,最左推导或最右推导的选择是否应该导致解析树的单一性？

[编辑:在这里回答]

2.1)但是,与k相关的语法是否模糊？我的意思是给出一个LR(2)语法,对于LR(1)解析器是不明确的,对于LR(2)解析器是不明确的？

[编辑:不,不是,LR(2)语法意味着解析器将需要两个前瞻标记来选择正确的规则来使用.另一方面,模糊语法是可能导致多个解析树的语法.]

2.2)所以一个LR(*)解析器,只要你能想象它,根本就没有模糊的语法,然后可以解析整套无上下文语言？

[编辑:由Ira Baxter回答,LR(*)不如GLR强大,因为它无法处理多个解析树.]

3)根据以前的答案,以下内容可能是自相矛盾的.考虑到LR解析,模糊语法会引发shift-reduce冲突吗？一个明确的语法也会引发一个吗？以同样的方式,减少 - 减少冲突怎么样？

[编辑:就是这样,模糊的语法导致转移减少和减少 - 减少冲突.通过对立,如果没有冲突,语法是单义的.]

4)解析左递归语法的能力是LR(k)解析器优于LL(k)的优势,它们之间的唯一区别是什么？

[编辑:是的.]

5)给G1:

G1 :
S -> S + S
S -> S - S
S -> a

5.1)G1是左递归,右递归和模糊,我是对的吗？它是LR(2)语法吗？人们会明白这一点:

G2 :
S -> S + a
S -> S - a
S -> a

5.2)G2仍然含糊不清吗？G2的解析器是否需要两个前瞻？通过分解,我们有:

G3 :
S -> S V
V -> + a
V -> - a
S -> …

这篇关于浏览器如何工作的文章解释了CSS如何无上下文,而HTML则没有.但是JavaScript呢,JavaScript上下文是免费的吗？

我正在学习CFG和正式证明,但距离理解如何解决这个问题还有很长的路要走.有没有人知道JavaScript是否没有上下文？

这是一个家庭作业问题,我知道我没有错误地回答.我给了:

S -> ''

意味着S产生空字符串.我知道空集和空字符串不一样.据我的教授说,答案是:

S -> S

现在,这个答案对我来说似乎很奇怪:

1. 它永远不会终止.
2. 它不是一种语言,而是缺少一种语言.

我从严格的数学角度理解,我不会得到第二个任何地方.但是,语言是否需要终止？拥有一种可以永远持续下去的语言听起来没问题,但是一个永远不会终止的语言听起来不够错,我以为我会问是否有人知道这是否是语言要求.

我有这个正则表达式:

regex = %r{\A(?<foo> a\g<foo>a | b\g<foo>b | c)\Z}x

当我针对几个字符串测试它时,它看起来像上下文无关语法一样强大,因为它正确处理递归.

regex.match("aaacaaa")
# => #<MatchData "aaacaaa" foo:"aaacaaa">
regex.match("aacaa")
# => #<MatchData "aacaa" foo:"aacaa">
regex.match("aabcbaa")
# => #<MatchData "aabcbaa" foo:"aabcbaa">
regex.match("aaacaa")
# => nil

" Ruby 1.9正则表达式的乐趣 "有一个例子,他实际上安排了一个正则表达式的所有部分,使它看起来像一个无上下文的语法,如下所示:

sentence = %r{ 
    (?<subject>   cat   | dog   | gerbil    ){0} 
    (?<verb>      eats  | drinks| generates ){0} 
    (?<object>    water | bones | PDFs      ){0} 
    (?<adjective> big   | small | smelly    ){0} 

    (?<opt_adj>   (\g<adjective>\s)?     ){0} 

    The\s\g<opt_adj>\g<subject>\s\g<verb>\s\g<opt_adj>\g<object> 
}x

在他重新排列正则表达式部分的技术和我的递归命名捕获组的例子之间,这是否意味着Ruby 1.9正则表达式具有与无上下文语法相当的能力？

我想知道是否可以直接使用CFG或PEG语法作为代码完成的基础而无需修改.我听说IDE中的代码完成有时会被操纵和按摩,甚至是硬编码,因此它的性能更好.

我想在一个小型DSL上完成代码编写,所以我完全理解一个语法不能帮助一个具有库函数等知识的代码完成系统.

据我所知,解析器本身至少需要提供一个系统来查询接下来的内容.

特别是我对使用peg.js 或jison的javascript代码完成解决方案感兴趣

在Web上,有很多示例显示如何从LL(1)解析器的第一个/后续集合构造用于无上下文语法的解析表.

但我没有找到任何与k> 1个案例相关的有用信息.甚至维基百科也没有提供相关信息.

我希望它必须在某种程度上相似,但指向这一领域现有研究的指针将非常有帮助.