标签: context-free-grammar

R: S ---> aSb\n   S ---> SS\n   S ---> \xce\xb5\n

我应该如何编写这些表达式的语法？

这样写是真的吗？

G = ({S}, {a, b}, {S ---> aSb, S ---> SS, S ---> \xce\xb5}, {S})\n

或者像这样（将 epsilon 添加到终端）：

G = ({S}, {a, b, \xce\xb5}, {S ---> aSb, S ---> SS, S ---> \xce\xb5}, {S})\n

哪个是正确的？

以图的形式构造确定性有限自动机的规则是什么？我的教授通过例子解释,但我不确定所有图表必须遵循哪些规则.任何帮助表示赞赏,谢谢!

我正在从Aho的编译器构造中读取有限自动机和语法,并且我长期坚持使用这种语法.我对如何描述它没有明确的认识:

考虑以下语法:

S - >(L)| a L - > L,S | 小号

请注意,括号和逗号实际上是该语言的终端,并出现在此语法接受的句子中.尝试描述该语法生成​​的语言.这个语法是不明确的？

我关注的是:这种语法生成的语言能否被描述为正则表达式？我对如何做到这一点很困惑.有帮助吗？

所以我一直在尝试用Scala的解析器编写一个计算器,它很有趣,除了我发现操作符关联性是倒退的,当我试图让我的语法左递归时,即使它完全是明确的,我得到了堆栈溢出.

为了澄清,如果我有一个规则,如:def减法:Parser [Int] = num~" - "~add {x => x._1._1 - x._2}然后评估7 - 4 - 3出来是6而不是0.

我实际实现这个的方式是我正在组成一个二叉树,其中运算符是非叶节点,叶节点是数字.我评估树的方式是留给孩子(操作员)的右孩子.在为7 - 4 - 5构建树时,我希望它看起来像是:

-
-   5
7   4   NULL   NULL

其中 - 是根,其子节点是 - 和5,第二个孩子是7和4.

但是,我能够轻松构建的唯一树是

-
7   -
NULL   NULL   4   5

这是不同的,而不是我想要的.

基本上,简单的括号是7 - (4 - 5),而我想要(7 - 4) - 5.

我怎么能破解这个？无论如何,我觉得我应该能够编写一个具有正确运算符优先级的计算器.我应该首先对所有内容进行标记,然后反转我的令牌吗？我是否可以通过抓住正确孩子的所有左子女并让他们成为正确孩子的父母的正确孩子并让父母成为前右孩子的左孩子来翻转我的树？它在第一次近似似乎很好,但我并没有真正考虑过它.我觉得必须有一些我不知道的情况.

我的印象是我只能使用scala解析器创建一个LL解析器.如果您了解其他方式,请告诉我!

在定义语法时,请说一个语法来评估算术表达式:我们将表达式划分为术语和因子,如下所示:

E ::= E + T  
T ::= T * F  
F ::= num  
    | (E)  

然后我们需要解决左递归问题.

那么为什么不这样定义语法:

E ::= T + E  
T ::= F * T  
F := num  
    | (E)  

并且只有正确的递归.

我是那种一卡与自动机和语法问题.我搜索了很多但没有成功.

它甚至有可能构建一个语法生成这种语言L？

 L = { a(2i) | i >= 0} 

谁能为我提供简单的解决方案？

也许是一个相当深入的问题,但是有人知道为什么会这样

Java语言规范 - Java SE 8 Edition(2014-03-03)

它根据生产规则和终端定义了Java 8的正式无上下文语法,并不是所有已定义的规则都可以访问？

规范描述了许多规则,如

IfThenStatement:
if(Expression)Statement

要么

AssertStatement:
断言表达式;
断言表达式:表达;

这一切都很有意义.

但奇怪的是,一些定义的规则是其他人无法达到的,例如重要的规则

类型:
PrimitiveType
ReferenceType

总的来说,我计算了以下两条规则:其他人无法访问的规则:

1. 包裹名字
2. 类型

如何定义具有无法访问规则的完整Java 8 CFG？

我正在寻找一个详细的算法,描述如何在无上下文语法中为非终端符号生成前导和尾随集.

我发现了这样的东西:https: //pl.scribd.com/doc/51358638/16/Operator-Precedence-Relations 但我不确定它是如何工作的.(见第20页)

假设我们有制作:

A - > YaZ | 乙

B - > b

然后,据说,前导(A)= {a},前导(A)=前导(B)和前导(B)= {b}.我对此表示怀疑:

1. 这是否意味着,领导(A)= {a,b}？ - 我假设在每一步中我们都不会因为'='而替换已生成的集合,而是将两个集合之和.
2. 这是否意味着,领导(B)是{b}还是{a,b}？ - 第三条规则是否意味着我们将前导(B)添加到前导(A)或前导(A)和前导(B)是等效的？

我们有一些带有用户输入的字段；到目前为止，验证该内容的规则是[A-Z][A-Z0-9]{0,7}。含义：任何具有至少一个字符的大写单词；从角色开始；整个单词最多8个字符。

现在，我被告知我们也应该接受“尾随”空格。但当然-仅尾随空格。更新；第一个答案是错误的：整个单词的最大长度仍然是8个字符！因为这正是促使我提出这个问题的要点。

我猜这可以用两个表达式检查：
a）[A-Z][A-Z0-9 ]{0,7}必须匹配输入，
b）[ ][A-Z0-9]必须不匹配输入

（第二个表达式只是查找任何“非跟踪”空间）

但是，还有一个可用于检查这种情况的正则表达式吗？

还是在这种情况下，虽然运气好-正则表达式只接受上下文无关的语法？

我用Java编写了一个解析器生成器,经过几次颠簸(例如早期版本并不特别喜欢左递归),我设法让它与一些简单的语法一起工作(所以我可以手工验证产品是否正确我试着给它一个更复杂的语法,输出结果是它不是一个LR(1)语法(源于解析后试图在解析表中的同一个单元格上写两次)

有问题的语法是

S-> aAb | SA
A-> aA | e | S.

我很确定这个语法是LR(1),无论如何,这是我程序的输出 http://pastebin.com/hJNC9uuN

任何建议都将是最宝贵的谢谢(如果有人有一个解析器生成器输出自动机和解析表,所以我可以面对它们更好)