标签: context-free-grammar

L = {ww | w属于{0,1}*}的补语的CFG是多少？

我对上下文无关语法中的歧义概念并不十分清楚.如果有人可以帮助我解释这个概念或提供一个好的资源,我会非常感激.

有人可以用外行的话来解释:

1. 什么是无上下文语法？

2. Backus Naur表格是什么？

3. 如何使用这种表示法？

4. 如何进行字符串派生？

5. 如何描述语言语法？

无上下文语言和常规语言的交集始终是无上下文的,但是在集合交集下不关闭无上下文语言.任何人都可以解释为什么如果所有常规语言都没有上下文,两个定理都是正确的(相反的情况并非总是如此)？

我无法理解为什么这个简单的语法 -

grammar Test;
file    :   ID;
ID  :   .*;

导致此错误 -

Test.g:3:6: The following alternatives can never be matched: 1

为什么会这样？

鉴于CFG

S --> a S b | c | d

我想写一个谓词,如语法('S',句子),它可以产生所有可能的

sentences like
sentence=acb,
sentence=acd,
sentence=c,
sentence=ab......................

使用最左边的推导,如果遇到的符号是终端,它应该打印出该终端,如果遇到的符号是非终端 'S',它应该回溯并替换其中一个语法a S b或c或d并重复处理.

我不想要任何代码......只是帮我提一些如何开始的提示

我在堆栈溢出中找到了与"多个替代"相关的问题,但没有什么有用的.这是我在antlr3中的g文件的一部分.

statement:
    selection_stmt
    | expression_stmt 
    | compound_stmt
    | iteration_stmt
    | return_stmt
    ;

selection_stmt:
    IF OPENB expression CLOSB statement (ELSE statement)?
    ;

expression:
    (var ASSIGN expression) => assignment 
    | simple_expression
    ;

我面临的问题是我收到上述短语的警告ELSE statement.

(200):决策可以使用多个备选方案匹配输入,例如"ELSE":1,2结果,对于该输入禁用了备选方案2

谁能解释一下这里发生了什么？谢谢.

PS当我使用句法谓词时((ELSE)=>ELSE statement)?,警告消失.我也不明白这个原因.

LR(1)解析器可以解析这种类型的语法吗？

S -> SA  | A
A -> aSb | ab

我正在尝试编写一个实现这种类型解析器的Java程序,但是我只能在没有左递归的语法上得到正确的结果.

从这个问题,涉及二进制运算符(+ - */)的表达式的语法不允许使用外括号:

top_level   : expression PLUS term
            | expression MINUS term
            | term TIMES factor
            | term DIVIDE factor
            | NUMBER
expression  : expression PLUS term
            | expression MINUS term
            | term
term        : term TIMES factor
            | term DIVIDE factor
            | factor
factor      : NUMBER
            | LPAREN expression RPAREN

这个语法是LALR(1).因此,我能够使用PLY(yacc的Python实现)为语法创建自下而上的解析器.

为了进行比较,我现在想尝试为同一种语言构建一个自上而下的递归下降解析器.我已经改变了语法,删除了左递归并应用了左因子:

top_level   : expression top_level1
            | term top_level2
            | NUMBER
top_level1  : PLUS term
            | MINUS term
top_level2  : TIMES factor
            | …

我有一个例句。“开门。” 我解析了一个句子以获取括号内的解析输出，如下所示。

（S（VP（VB打开）（NP（DT the）（NN门）））（..））

我需要提取产生已解析输出的CFG语法规则。我可以这样手动将它们写出来：

grammar = CFG.fromstring("""   
S -> VP NP   
NP -> Det N   
VP -> V   
Det ->'the '   
N -> 'door'   
V -> 'Open'   
""")  

但这很耗时，如何自动生成带括号的语法规则？