多年来,"正则表达式"模式匹配越来越强大,我想知道:它真的只是上下文敏感 - 语法匹配吗？它是无上下文语法匹配的变体/扩展吗？它现在在哪里,为什么我们不称之为旧的,限制性的"正则表达式"？
我在Internet上找不到关于LL(*)解析器的任何完整描述,例如ANTLR.
我想知道LL(k)解析器和LL(*)之间的区别是什么,以及为什么它们不能支持left-recusrive语法,尽管它们具有灵活性.
Python中有哪些工具可以帮助解析无上下文语法？
当然可以自己滚动,但我正在寻找一个可以为给定的CFG生成解析器的通用工具.
我们知道,给定一个常规语法,我们有算法来获得它的正则表达式.
但是如果给定的语法是无上下文语法(但它只生成常规语言),就像
S->aAb
A->bB
B->cB|d
S->aAb
A->bB
B->cB|d
S->aAb
A->bB
B->cB|d
是否有任何现有算法可以获得正则表达式？
谢谢!
我正在研究一个带有Unicode字符的非英语解析器.为此,我决定使用NLTK.
但它需要一个预定义的无上下文语法,如下所示:
S -> NP VP
VP -> V NP | V NP PP
PP -> P NP
V -> "saw" | "ate" | "walked"
NP -> "John" | "Mary" | "Bob" | Det N | Det N PP
Det -> "a" | "an" | "the" | "my"
N -> "man" | "dog" | "cat" | "telescope" | "park"
P -> "in" | "on" | "by" | "with"
在我的应用程序中,我应该使用基于规则的语法来最小化硬编码.例如,我可以假设以-ed或-ing结尾的任何单词作为动词.所以它应该适用于任何给定的上下文.
如何将这些语法规则提供给NLTK？或者使用有限状态机动态生成它们？
如何找到属性是从语法的产生中合成还是继承？
我想因为必须在问题中预定义属性 - 如果它的值取决于子节点或父节点.但有没有办法分析属性是从语法产生继承还是合成.
compiler-construction parsing abstract-syntax-tree context-free-grammar semantic-analysis
根据维基百科上的"递归下降解析器",只有LL(k)语法才能实现没有回溯(也就是预测解析)的递归下降.
在其他地方,我已经读过Lua的实现使用这样的解析器.但是,该语言不是 LL(k).事实上,Lua天生就是含糊不清的:是a = f(g)(h)[i] = 1指a = f(g); (h)[i] = 1还是a = f; (g)(h)[i] = 1？这种歧义通过解析器中的贪婪来解决(因此上面被解析为错误的a = f(g)(h)[i]; = 1).
这个例子似乎表明预测解析器可以处理不是LL(k)的语法.事实上,它们是否能够处理LL(k)的超集？如果是这样,有没有办法找出一个给定的语法是否在这个超集中？
换句话说,如果我正在设计一种我想使用预测解析器解析的语言,我是否需要将语言限制为LL(k)？或者我可以适用更宽松的限制吗？
lua parsing recursive-descent context-free-grammar ll-grammar
有没有人知道包含典型编译器课程的在线课程/大学讲座？我有计算理论但不幸的是我的学校没有提供编译器构建课程.
我知道那里有讲座; 我希望能为特别好的产品提供建议.
还有新手到现场的书吗？除了龙书之外,至少还有一些东西.初学者水平很好,我知道市场上有很多中级高级文本.
谢谢!
我需要一个CFG,它会生成除了回文之外的字符串.已提供解决方案,如下所示.(计算理论导论 - Sipser)
R -> XRX | S
S -> aTb | bTa
T -> XTX | X | <epsilon>
X -> a | b
我对这个语法的工作方式有了一般的了解.它要求插入一个子串,该子串在其两半上通过生产具有相应的不相等的字母S -> aTb | bTa,从而确保永远不会产生回文.
我将按照我的理解写下前两部作品的语义,
S 生成不能成为回文的字符串,因为它们的第一个和最后一个字母不相等R由至少一个S作为子串组成,确保它永远不是回文.我不完全理解第三个产品的语义,即.
T -> XTX | X | <epsilon>
X -> a | b
我看到它的方式,T可以生成a和b的任意组合,即{a,b}*.为什么它不会像
T -> XT | <epsilon>
X -> a | b
这不是两个相同的？由于后者更直观,为什么不使用它？
我正在阅读Java语言规范8.
我试图理解第2章.语法.
这是我已经学到的:
语义学:
语义学是对意义的研究.
含义:
在语义中,含义被定义为扩展:世界中单词/短语所指的东西,加上意图:单词/短语唤起的概念/心理图像.
语法:
语法是关于句子的结构,以及决定哪些单词去哪里的内容.
生产:
计算机科学中的生产或生产规则是指定符号替换的重写规则,可以递归地执行符号替换以生成新的符号序列.
字母:
非空集在被指示用于字符串操作时称为字母表.
Lexeme:
lexeme是一串字符,形成一个句法单位.
句法单位:
句子是"最高"(即最大)的句法单位,
最低(即最小)的句法单位是单词,
中间句法单位是短语.
令牌:
令牌是表示词汇的结构,该词汇明确指出其用于解析的分类.
语法:
语法(当没有给出上下文时,为了清楚起见通常称为正式语法)是一组用于正式语言的字符串的生成规则.规则描述了如何根据语言的语法从语言的字母表中形成有效的字符串.形式语法是一组用于重写字符串的规则,以及重写开始的"起始符号".
我无法找出语法语法是什么.