c - C 代码中的递归下降解析器

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 6 年前。

Improve this question

我想用 C 语言制作递归下降解析器。给定条件如下:

<prg> -> <stmts>
<stmts> -> <stmt> [;stmts]
<stmt> -> <assign> | <if>
<if> -> if '(' <expr> ')' ('{' <stmts> '}' | <stmt>)
<expr> -> <term> {(+ | -) <term>
<term> -> <factor> {(* | / ) <factor>}
<factor> -> <const> | <id> | '(' <expr> ')'

<id> -> <letter> {<letter>|<const>}
<letter> -> a|b|c
<digit> -> 0|1|2

我得到了 addChar()、getChar()、lex() 函数。我想知道如何处理“<”stmt>，“<”if>，“<”letter>。另外，什么意思 [;stmts] 和 {"<"字母>|"<"常量>}？

Answer 1

请参阅我对 how to write recursive descent parsers 的回答:

你从哪里得到这个语法的？不幸的是，人们在 BNF 中使用各种略有不同的符号编写语法，并且不会告诉您他们使用的约定。检查Wikipedia for BNF查看一些变化。

通常，您必须了解您对 BNF 及其变体的理解，以及您对 BNF 旨在描述的语言的理解，并解释 BNF 以猜测它们的实际含义。 [那是愚蠢的； BNF 的目的是消除所有猜测]。关于

[;stmts]

并利用大多数语言允许语句序列的知识，我猜[ X ]表示“序列中的 0 个或多个 X”，这里的具体解释表示“0 个或多个语句，每个语句前面都有一个 ';'”。

按照惯例，概念 X 的 BNF 规则被引用为 <X> ，这个语法在这里被破坏了；作者很草率，应该写[; <stmts>] .

看来，在此 BNF 样式中指示文字字符的约定是，当文字字符不是 BNF 元语法中使用的字符时，就使用文字字符。使用的 BNF 元语法字符是该语法，看起来是

  < >   ( ) [  ]  {  }  ' 

与->作为特殊的标记。任何不在这个集合中的文字字符都简单地写成它自己；该集中的任何文字字符都必须用引号引起来。这种解释似乎解释了除 - 之外的大部分语法。 。这样的规则可能会让作者看起来(某种程度上)更清晰的语法，但会让读者难以理解。

无论如何，这解释了为什么 [; stmts]不写为 [ ';' stmts] 。恕我直言，正确的约定是始终引用文字字符；那么读者就永远不必猜测。

关于

{<letter>|<const>}

再次利用我们对 BNF 变体的理解，并且知道标识符通常是字母和数字的序列，我得出结论 { X } ”的意思是“0个或多个X”，这里的意图是“0个或多个字母或数字”。

事实上我解释了 [ X ]和{ X } as 意思是“0或更多”表明我的猜测是错误的；为什么使用两种不同的符号来表示同一件事？所以也许它们的含义不同；也许[ X ]意思是“一个或多个”。光看语法是无法判断的。

事实上，我必须为这么小的语法猜测这么多，这是个坏消息。我认为这位语法作者选择的约定对读者来说是一种伤害。这对于初学者来说尤其是坏消息，因为它给本已棘手的主题增添了困惑。

我代表编写此语法并将其提供给您的人表示歉意。

但是，吸取教训吧。 BNF 文法在很多情况下都是写得很草率的。由于您无法确定作者，因此您需要学会解释您所得到的内容。真糟糕。