解析“简单”语法

Question

提前道歉，我相信对于习惯于使用解析器和语法的人来说，这个问题几乎看起来很蠢，但对我来说这些都是陌生的主题，这是我尝试慢慢进入需要它们的实际情况。

我想为以下“语言”编写一个解析器，其中包含一个看起来像这样的单个“特殊结构”：

\command[ options ]{ contents }

内容可以是任何东西，包括嵌套命令，并且可能包含转义的括号或反斜杠\{ \} \\。我意识到“任何东西”并不具体，但理想情况下，它们应该通过匹配括号（不包括转义的括号）来确定，如果可能的话。

选项应该是逗号分隔的赋值表达式列表，例如name = value，但值可能是包含=或,字符的带引号字符串。最后，前一个name和command应该验证正则表达式\w[\w\d\._-+*]*——即，第一个字符应该是字母，剩余的字符应该是字母、数字或. _ - + *中的一个。

使用正则表达式编写这个问题似乎过于复杂（例如，因为值可能包含带引号的字符, =，否则会分离赋值或名称/值对）。因此，我认为这里最合适的工具是语法，但尽管表面读起来很简单，但我不确定如何编写它（BNF、PEG等？），使用哪种类型的解析器（LR、递归下降等？），以及如何在实际程序中使用解析输出。

我希望得到用Python解释的答案，但如果必要或更适合，当然可以使用其他工具的组合。

---

注意：这不是关于LaTeX的问题。我意识到它们相似，但是LaTeX比之前的语言复杂得多，例如字符代码取决于上下文。我只是在寻求一个实际的例子，它（我认为）足够简单，适合SO，但在我的日常工作中已经非常有用。

- Jonathan H

---

这是（La）TeX吗？ - Willem Van Onsem

读到一个标题中带有“解析”一词的问题，而且它实际上确实是关于解析的，真是让人耳目一新。 - Jared Smith

“内容可以是任何东西”从编写解析器的角度来看并没有提供太多信息。 - John Coleman

如果内容有内部结构，那么你需要详细说明它，特别是如果你要使用期望有输入语法的解析器生成工具。 - John Coleman

很久以前，我曾经看过 http://simpleparse.sourceforge.net/ 来解析 SQL。但由于 a）它不是高优先级的事情； b）它的文档不是非常好，我不能快速地弄清楚它如何处理保留字，例如 AND、FROM 等等…… 因此我放弃了。尽管如此，它看起来还是相当强大的。 - JL Peyret

Answer 1

从更正式的角度出发，用您喜欢的符号表示语法。例如，根据您的描述，EBNF 可以表示为：

program := element+
element := command | literal
literal := (not '\')+

command := '\'identifier options? '{' program '}'
options := option | options ',' option
option  := identifier '=' value
value   := number | string

string  := '"' (escape | not '\' or '"')* '"'
escape  : = '\' char

然后，将这个内容传递给解析器生成器（pyParsing、pyYACC、ANTLR）或手写一个解析器。在后一种情况下，自上而下是最简单的选项：从语法的顶部开始，将每个规则转换为一个函数，该函数将返回已解析的AST节点并消耗输入，或者返回无或抛出异常。例如：

 def program():
    elements = []
    while next_sym():
        elements.append(element())
    return {'type': 'program', 'children': elements}

 def element():
     return command() or literal()

 def command():
     if next_sym() == '\\':
         get_sym()
         ...parse command here
         return {'type': 'command', 'children': ...}
     return None 

next_sym从输入中返回下一个符号（在EOF时返回None），而get_sym则消耗该符号并推进输入缓冲区。

- georg

---

非常感谢。在这个例子中，identifier、number和char是原语吗？还是应该像您定义其余部分一样定义它们？关于string的定义，部分内容not '\' or '"'强制反斜杠和双引号进行转义，这正确吗？ - Jonathan H

根据您使用的方法不同，有些生成器提供了这方面的原语，而有些则没有，因此您将不得不使用正则表达式来定义它们。 - georg