标签: context-free-grammar

以 NLTK 的文档为例的“正则表达式”和同一个 CFG 之间在功率上有什么实际区别吗？肯定应该有，因为有不规则的上下文无关语言，但我找不到一个具体的例子，其中 CFG 方法胜过正则表达式。

http://nltk.org/book/ch07.html

我正在实现 pratt 的自上而下的运算符优先级解析器，我想知道它属于哪个正式类别 - 是 LR(1) 吗？

为 k > 1 制作人工 LR(k) 文法很容易：

Input: A1 B x
Input: A2 B y                   (introduce reduce-reduce conflict for terminal a)
A1   : a
A2   : a
B    : b b b ... b              (terminal b occurs k-1 times)

然而，是否有任何现实世界的非 LR(1) 计算机语言是 LR(k > 1) 可解析的？
或者非 LR(1) 语言也不是 LR(k)？

我目前正在浏览CFG，看到了答案，但不确定他们是如何得到的。他们是如何在这里将其从CFG转换为正则表达式的？

S -> aS|bX|a
X -> aX|bY|a
Y -> aY|a


answer:
R.E -> (a*(a+ba*a+ba*ba*a))

我正在尝试编写一个上下文无关语法来执行一些非常简单的操作\xe2\x80\x94，将字符串解析为（1）行尾空格和（2）其他所有内容的交替部分的列表。例如：

This.first.line...\\n..and.this....second.line\\n.\\n..and.final.line\n

（为了可读性显示" "为"."和换行符"\\n"）被解析为

"This.first.line", "...\\n..", "and.this....second.line", "\\n.\\n..", "and.final.line"\n

我写了这个语法：

string = raw_start | newline_start\nraw_start = raw_section [newline_start]\nnewline_start = newline_section [raw_start]\nraw_section = {any_character_except_newline}\nnewline_section = {whitespace_except_newline} new_line {any_whitespace_character}\n

但这是不正确的，因为{any_character_except_newline}当我希望将那些包含在new_line_section.

是否可以说“使用空格，除非它们位于换行符之前”而不丢失语法的上下文无关属性？

我被要求给出一个生成以下语言的上下文无关文法（字母表是 {0, 1}：

{ w| w 是回文 }

为了正确回答这个问题，我需要知道是否可以将空字符串视为回文。谢谢你。

给定任意上下文无关语法，我如何检查它是否描述了常规语言？

我不是在寻找考试“技巧”。我正在寻找一种可以编写代码的万无一失的机械测试。

如果有帮助的话，这里是我可能会收到作为输入的 CFG 示例。具体来说，请注意，答案一定比仅仅寻找左递归或右递归复杂得多，因为另一种类型的递归的存在并不自动意味着语法是不规则的。

S: A B C D X
A: A a
A:
B: b B
B:
C: c C c
C: c
D: D d D
D: d
X: x Y
X:
Y: y X
Y:

所以问题是关于下面的语法。我正在研究一种小型解释语言（我们在课堂上学习了一些编译器设计，所以我想将其提升到一个新的水平并自己尝试一些东西）。我一直在尝试制作非终结符Expr。

Statement ::= Expr SC
Expr ::=           /* I need help here */
Assign ::= Name EQUAL Expr
AddSub ::= MulDiv {(+|-) AddSub}
MulDiv ::= Primary {(*|/) MulDiv}
Primary ::= INT | FLOAT | STR | LP Expr RP | Name
Name ::= ID {. Name}

Expr必须考虑Statement到以下两种情况：

1. x = 789;（常规赋值，后跟分号）
2. x+2;（没有赋值，只是计算，丢弃；后面跟一个分号）

第二个案例的目的是为未来更多的改变奠定基础。我正在考虑一元递增和递减运算符，以及函数调用；两者都不要求分配有意义。

我看过其他语法（即 C#），但它太复杂且冗长，难以理解。当然，我不是在寻找解决方案，而只是寻求如何修改语法的指导。

感谢所有帮助。

编辑：我应该说我最初的想法是Expr ::= Assign | AddSub，但这行不通，因为它会产生歧义，因为两者都可以以非终结符 开头Name。我已经制作了我的标记生成器，使其允许一个标记向前看（查看），但我没有为非终端制作这样的东西，因为它将尝试解决一个可以避免的问题（歧义）。在语法中，终结符是全部大写的。

我一直在尝试构建一个函数： concat('A','B') OR concat('A',9)

这是我写的示例语法：

    LPAREN : '(' ;
    RPAREN : ')' ;
    FUNCTIONNAME : 'CONCAT' ;
    ARGUMENTS : TEXT (',' TEXT)* ;
    TEXT : ('a'..'z' | '0'..'9' | 'A'..'Z')+; 
    allFunction : FUNCTIONNAME LPAREN ARGUMENTS (',' ARGUMENTS)* RPAREN ;

但无法正确构建一棵树。

更新1：

这是树：

  0 null
-- 11 CONCAT
-- 4 (
-- 13 2,5
-- 5 ) 

和语法：

allFunction : FUNCTIONNAME LPAREN ARGUMENTS RPAREN;

更新2：

语法：

allfunction : COMMA | FUNCTIONNAME LPAREN ARGUMENTS (COMMA ARGUMENTS)* RPAREN ;

解析输出：

CONCAT(A,B,C) …

假设我有以下 JS 代码部分：

const v = 3;

据我了解，它可以解析为AssignmentExpression：

AssignmentExpression :
    LeftHandSideExpression = AssignmentExpression

现在我想知道它是如何从Statement派生出来的？一种可能的途径是：

Statement -> ExpressionStatement -> Expression -> AssignmentExpression

但我不确定。这是正确的吗？

这是我找到它的方法：

AssignmentExpression是部分表达式：

Expression :
    AssignmentExpression
    Expression, AssignmentExpression

然后Expression是ExpressionStatement 的一部分是

ExpressionStatement:

    [lookahead ? { {, function, ..., let [ }] Expression;

然后ExpressionStatement是Statement 的一部分：

Statement :
    ExpressionStatement