标签: context-free-grammar

从这个维基百科页面:

无上下文语法和解析表达式语法之间的根本区别在于PEG的选择运算符是有序的.如果第一个替代方案成功,则忽略第二个替代方案.因此,有序选择不是可交换的,不像无上下文选择,如无上下文语法和正则表达式.有序选择类似于某些逻辑编程语言中可用的软切算子.

为什么PEG的选择算子会使匹配短路？是因为最小化内存使用量(由于记忆)？

我不确定正则表达式中的选择运算符是什么,但我们假设它是:/[aeiou]/匹配元音.所以这个正则表达式是可交换的,因为我可以用5个中的任何一个来编写它!元音字符的(五个阶乘)排列？即/[aeiou]/行为相同/[eiaou]/.它是可交换的有什么好处？(参见PEG的非交换性)

结果是,如果CFG直接音译为PEG,则通过从可能的解析中确定性地选择一个解析树来解决前者中的任何歧义.通过仔细选择指定语法备选的顺序,程序员可以很好地控制选择哪个解析树.

这说PEG的语法优于CFG吗？

我试图找到一个简单的(即非正式的)解释,正如乔姆斯基所阐述的4级正式语法(无限制,上下文敏感,无上下文,常规).

自从我学习正式语法以来,这已经是一个时代了,各种各样的定义现在让我难以想象.要明确的是,我不是在寻找你​​到处都可以找到的正式定义(例如这里和这里 - 我可以谷歌以及其他任何人),或者甚至是任何形式的正式定义.相反,我希望找到的是干净简单的解释,为了完整性而不牺牲清晰度.

在查看 C 的 BNF 语法时，我认为声明的产生式规则看起来很奇怪（根据https://cs.wmich.edu/~gupta/teaching/cs4850/sumII06/The%20syntax%20of% 20C%20in%20Backus-Naur%20form.htm）：

<declaration> ::=  {<declaration-specifier>}+ {<init-declarator>}* ;

为什么对 ? 使用*量词（表示出现零次或多次）init-declarator？这允许诸如int;或 之类的语句void;在语法上有效，即使它们在语义上无效。难道他们不能只在产生式规则中使用+量词（出现一次或多次）*吗？

我尝试编译一个简单的程序来查看编译器输出的内容，它所做的只是发出警告。

输入：

<declaration> ::=  {<declaration-specifier>}+ {<init-declarator>}* ;

输出：

int main(void) {
    int;
}

该标准是否指定了官方C++语法？

我搜索过,但没找到任何地方.

另外,我希望详细阅读一些关于C++语法的内容,比如它所属的语法类别等等.任何指向正确方向的链接都会有所帮助.

按类别,我的意思是

取自这里.

我曾经认为C++是"怪异"的一个与所有与歧义<和>,而是试图实现一个解析器我想我找到打破一个例子之后几乎每一个使用的语言<和>泛型类型:

f(g<h, i>(j));

这可以在语法上解释为泛型方法call(g),也可以解释为给出f两次比较的结果.

这些语言(特别是Java,我认为应该是LALR(1) - 可解决的？)如何克服这种语法模糊性？

我无法想象任何非hacky/context-free方式来解决这个问题,我对这种语言如何无上下文感到困惑,更不用说LALR(1)-parsable ......

(值得注意的是,即使是GLR解析器也无法为此语句返回单个解析而没有上下文!!)

我一直在使用以下数据结构来表示Haskell中的命题逻辑:

data Prop 
    = Pred  String
    | Not   Prop
    | And   Prop Prop
    | Or    Prop Prop
    | Impl  Prop Prop
    | Equiv Prop Prop
    deriving (Eq, Ord)

欢迎对此结构发表任何评论.

但是,现在我想扩展我的算法来处理FOL - 谓词逻辑.什么是在Haskell中代表FOL的好方法？

我见过的版本 - 几乎是 - 上面的扩展,以及基于更经典的无上下文语法的版本.有没有关于此的文献,可以推荐吗？

如何知道语言是否无上下文？

似乎递归下降解析器不仅是最简单的解释,而且最简单的设计和维护.它们不仅限于LALR(1)语法,并且代码本身可以被凡人理解.相比之下,自下而上的解析器对它们能够识别的语法有限制,并且需要由特殊工具生成(因为驱动它们的表几乎不可能手动生成).

那么为什么自下而上(即shift-reduce)解析比自上而下(即递归下降)解析更常见？

如何为要从头设计的新编程语言(命令式编程语言)定义语法(无上下文).

换句话说:当您想从头开始创建新的编程语言时,如何继续.

我不明白一个明确的语法是如何从一个含糊不清的语法中得出的？考虑现场示例:示例.如何得出的语法让我感到困惑.

有人可以指导我吗？