LALR-1 解析器生成器

一个 Erlang 的 LALR-1 解析器生成器，类似于 yacc。它以 BNF 语法定义作为输入，并生成用于解析器的 Erlang 代码。

要理解本文，您还必须查看 UNIX(TM) 手册中的 yacc 文档。这很可能是为了理解解析器生成器的概念，以及具有有限前瞻的 LALR 解析的原理和问题所必需的。

可以在 Brian W. Kernighan 和 Rob Pike 的 "The UNIX Programming Environment" 的第 8 章中找到对 yacc 的很好的介绍。

默认 Yecc 选项

（主机操作系统）环境变量 ERL_COMPILER_OPTIONS 可用于提供默认的 Yecc 选项。它的值必须是有效的 Erlang 项。如果该值是一个列表，则按原样使用。如果它不是一个列表，则将其放入一个列表。

该列表将附加到传递给 file/2 的任何选项。

可以使用 compile:env_compiler_options/0 来检索该列表。

预处理

yecc 模块中没有提供用于预处理要解析的文本（程序）的扫描器。扫描器充当一种词汇查找例程。可以编写一个仅使用字符标记作为终结符的语法，从而无需扫描器，但这会使解析器更大更慢。

用户应实现一个扫描器，该扫描器分割输入文本，并将其转换为一个或多个标记列表。每个标记都应是一个元组，其中包含有关语法类别、文本中的位置（例如行号）以及在文本中找到的实际终结符的信息：{类别, 位置, 符号}。

如果终结符是类别的唯一成员，并且符号名称与类别名称相同，则标记格式可以是 {符号, 位置}。

扫描器生成的标记列表应以解析器正在寻找的特殊 end_of_input 元组结尾。此元组的格式应为 {结束符号, 结束位置}，其中 结束符号 是一个与语法规则的所有终结符和非终结符类别不同的标识符。结束符号可以在语法文件中声明。

最简单的情况是将输入字符串分割为标识符（原子）列表，并将这些原子既用作标记的类别又用作值。例如，输入字符串 aaa bbb 777, X 可以扫描（标记化）为

[{aaa, 1}, {bbb, 1}, {777, 1}, {',' , 1}, {'X', 1},
 {'$end', 1}].

这假设这是输入文本的第一行，并且 '$end' 是一个特殊的 end_of_input 符号。

在编写新扫描器时，可以使用 io 模块中的 Erlang 扫描器作为起点。研究 yeccscan.erl，以了解如何在 io:scan_erl_form/3 之上添加过滤器，从而为 Yecc 提供扫描器，该扫描器在用 Yecc 解析器解析语法文件之前对其进行标记化。实现扫描器的更通用方法是使用扫描器生成器，例如 leex。

语法定义格式

语法文件中允许使用以 '%' 开头的 Erlang 风格的 注释。

每个 声明 或 规则 都以点（字符 '.'）结尾。

语法以可选的 header 部分开始。header 位于生成文件的开头，在模块声明之前。header 的目的是提供一种使 EDoc 生成的文档看起来更好的方法。每个 header 行都应包含在双引号中，并且新行将插入到行之间。例如

Header "%% Copyright (C)"
"%% @private"
"%% @Author John".

接下来声明要在规则中使用的 非终结符类别。例如

Nonterminals sentence nounphrase verbphrase.

非终结符类别可以在语法规则的左侧（= lhs 或 head）使用。它也可以出现在规则的右侧。

接下来声明 终结符类别，它们是扫描器生成的标记的类别。例如

Terminals article adjective noun verb.

终结符类别只能出现在语法规则的右侧（= rhs）。

接下来声明 根符号，或语法的起始类别。例如

Rootsymbol sentence.

此符号应出现在至少一个语法规则的 lhs 中。这是最通用的语法类别，解析器最终会将每个输入字符串解析为该类别。

在根符号声明之后，是您希望扫描器使用的 end_of_input 符号的可选声明。例如

Endsymbol '$end'.

接下来是（如果需要）一个或多个 运算符优先级 的声明。这些用于解决移位/规约冲突（请参阅 yacc 文档）。

运算符声明的示例

Right 100 '='.
Nonassoc 200 '==' '=/='.
Left 300 '+'.
Left 400 '*'.
Unary 500 '-'.

这些声明意味着 '=' 被定义为优先级为 100 的 右结合二元运算符，'==' 和 '=/=' 是 无结合性的运算符，'+' 和 '*' 是 左结合二元运算符，其中 '*' 的优先级高于 '+'（正常情况），并且 '-' 是优先级高于 '*' 的 一元运算符。'==' 没有结合性的事实意味着像 a == b == c 这样的表达式被认为是语法错误。

某些规则被分配了优先级：每个规则的优先级都来自规则右侧提到的最后一个终结符。也可以声明非终结符的优先级，“高一个级别”。当运算符重载时，这很实用（另请参阅下面的示例 3）。

接下来是 语法规则。每个规则的一般形式为

Left_hand_side -> Right_hand_side : Associated_code.

左侧是非终结符类别。右侧是一个或多个非终结符或终结符的序列，它们之间用空格分隔。关联代码是零个或多个 Erlang 表达式的序列（用逗号 ',' 作为分隔符）。如果关联代码为空，则也会省略分隔冒号 ':'。最后的点标记规则的结束。

诸如 '{'、'.' 等符号在用作语法规则中的终结符或非终结符时必须用单引号括起来。应避免使用符号 '$empty'、'$end' 和 '$undefined'。

语法文件的最后一部分是带有 Erlang 代码（= 函数定义）的可选部分，该部分“按原样”包含在生成的解析器文件中。此部分必须以伪声明或关键字开头

Erlang code.

在此部分之后，不得有任何语法规则定义或其他声明。为避免与内部变量冲突，请勿在此部分或与各个语法规则关联的代码中使用以两个下划线字符 ('__') 开头的变量名。

可选的 expect 声明可以放在最后的可选 Erlang 代码部分之前的任何位置。它用于抑制通常在语法不明确时给出的关于冲突的警告。一个例子

Expect 2.

如果移位/规约冲突的数量与 2 不同，或者存在规约/规约冲突，则会发出警告。

示例

用于解析列表表达式的语法（带有空的关联代码）

Nonterminals list elements element.
Terminals atom '(' ')'.
Rootsymbol list.
list -> '(' ')'.
list -> '(' elements ')'.
elements -> element.
elements -> element elements.
element -> atom.
element -> list.

此语法可用于生成一个解析器，该解析器解析列表表达式，例如 (), (a), (peter charles), (a (b c) d (())), ...，前提是您的扫描器将输入 (peter charles) 标记化，如下所示

[{'(', 1} , {atom, 1, peter}, {atom, 1, charles}, {')', 1},
 {'$end', 1}]

当解析器使用语法规则来解析（部分）输入字符串作为语法短语时，将评估关联的代码，并且最后一个表达式的值将成为已解析短语的值。解析器稍后可以使用此值来构建结构，这些结构是当前短语所属的更高短语的值。最初与终结符类别短语（即输入标记）关联的值是标记元组本身。

以下是上面添加了结构构建代码的语法示例

list -> '(' ')' : nil.
list -> '(' elements ')' : '$2'.
elements -> element : {cons, '$1', nil}.
elements -> element elements : {cons, '$1', '$2'}.
element -> atom : '$1'.
element -> list : '$1'.

在将此代码添加到语法规则后，解析器在解析输入字符串 (a b c). 时会生成以下值（结构）。这仍然假设这是扫描器标记化的第一个输入行

{cons, {atom, 1, a}, {cons, {atom, 1, b},
                            {cons, {atom, 1, c}, nil}}}

关联的代码包含 伪变量 '$1'、'$2'、'$3' 等，它们引用（绑定到）解析器先前与规则右侧的符号关联的值。当这些符号是终结符类别时，这些值是输入字符串的标记元组（参见上文）。

关联的代码不仅可以用于构建与短语关联的结构，还可以用于在解析过程中进行语法和语义测试、打印操作（例如用于跟踪）等。由于标记包含位置（行号）信息，因此可以生成包含行号的错误消息。如果规则的右侧之后没有关联的代码，则该短语与值 '$undefined' 关联。

语法规则的右侧可以为空。这可以通过使用特殊符号 '$empty' 作为 rhs 来指示。那么上面的列表语法可以简化为

list -> '(' elements ')' : '$2'.
elements -> element elements : {cons, '$1', '$2'}.
elements -> '$empty' : nil.
element -> atom : '$1'.
element -> list : '$1'.

生成解析器

要调用解析器生成器，请使用以下命令

yecc:file(Grammarfile).

如果语法不是 LALR 类型（例如，过于模糊），则会显示来自 Yecc 的错误消息。如果没有运算符优先级声明，则移位/规约冲突将有利于移位。请参阅 yacc 文档，了解如何使用运算符优先级。

输出文件包含解析器模块的 Erlang 源代码，模块名称与 Parserfile 参数相等。编译后，可以按如下方式调用解析器（假设模块名称为 myparser）

myparser:parse(myscanner:scan(Inport))

如果在生成解析器时包含了自定义序言文件而不是默认文件 lib/parsetools/include/yeccpre.hrl，则调用格式可能会有所不同。

使用标准序言，此调用将返回 {ok, Result}，其中 Result 是语法文件的 Erlang 代码构建的结构，或者如果输入中存在语法错误，则返回 {error, {Position, Module, Message}}。

Message 可以通过调用 Module:format_error(Message) 转换为字符串，并使用 io:format/3 打印出来。

注意

默认情况下，生成的解析器不会将错误消息打印到屏幕上。用户必须通过打印返回的错误消息，或者在与语法文件的语法规则关联的 Erlang 代码中插入测试和打印指令来完成此操作。

如果使用以下调用格式，也可以使解析器在需要时请求更多输入标记

myparser:parse_and_scan({Function, Args})
myparser:parse_and_scan({Mod, Tokenizer, Args})

分词器 Function 是一个函数或一个元组 {Mod, Tokenizer}。每当需要新标记时，就会执行调用 apply(Function, Args) 或 apply({Mod, Tokenizer}, Args)。例如，这使得可以逐个标记地从文件中进行解析。

上面使用的分词器必须实现为返回以下内容之一

{ok, Tokens, EndPosition}
{eof, EndPosition}
{error, Error_description, EndPosition}

这符合 Erlang io 库模块中扫描器使用的格式。

如果立即返回 {eof, EndPosition}，则对 parse_and_scan/1 的调用将返回 {ok, eof}。如果在解析器期望输入结束之前返回 {eof, EndPosition}，则 parse_and_scan/1 当然会返回错误消息（请参见上文）。否则，将返回 {ok, Result}。

更多示例

1. 一个将中缀算术表达式解析为前缀表示法的语法，不带运算符优先级

Nonterminals E T F.
Terminals '+' '*' '(' ')' number.
Rootsymbol E.
E -> E '+' T: {'$2', '$1', '$3'}.
E -> T : '$1'.
T -> T '*' F: {'$2', '$1', '$3'}.
T -> F : '$1'.
F -> '(' E ')' : '$2'.
F -> number : '$1'.

2. 带有运算符优先级的相同语法变得更简单

Nonterminals E.
Terminals '+' '*' '(' ')' number.
Rootsymbol E.
Left 100 '+'.
Left 200 '*'.
E -> E '+' E : {'$2', '$1', '$3'}.
E -> E '*' E : {'$2', '$1', '$3'}.
E -> '(' E ')' : '$2'.
E -> number : '$1'.

3. 一个重载的减号运算符

Nonterminals E uminus.
Terminals '*' '-' number.
Rootsymbol E.

Left 100 '-'.
Left 200 '*'.
Unary 300 uminus.

E -> E '-' E.
E -> E '*' E.
E -> uminus.
E -> number.

uminus -> '-' E.

4. 用于解析语法文件的 Yecc 语法，包括它本身

Nonterminals
grammar declaration rule head symbol symbols attached_code
token tokens.
Terminals
atom float integer reserved_symbol reserved_word string char var
'->' ':' dot.
Rootsymbol grammar.
Endsymbol '$end'.
grammar -> declaration : '$1'.
grammar -> rule : '$1'.
declaration -> symbol symbols dot: {'$1', '$2'}.
rule -> head '->' symbols attached_code dot: {rule, ['$1' | '$3'],
        '$4'}.
head -> symbol : '$1'.
symbols -> symbol : ['$1'].
symbols -> symbol symbols : ['$1' | '$2'].
attached_code -> ':' tokens : {erlang_code, '$2'}.
attached_code -> '$empty' : {erlang_code,
                 [{atom, 0, '$undefined'}]}.
tokens -> token : ['$1'].
tokens -> token tokens : ['$1' | '$2'].
symbol -> var : value_of('$1').
symbol -> atom : value_of('$1').
symbol -> integer : value_of('$1').
symbol -> reserved_word : value_of('$1').
token -> var : '$1'.
token -> atom : '$1'.
token -> float : '$1'.
token -> integer : '$1'.
token -> string : '$1'.
token -> char : '$1'.
token -> reserved_symbol : {value_of('$1'), line_of('$1')}.
token -> reserved_word : {value_of('$1'), line_of('$1')}.
token -> '->' : {'->', line_of('$1')}.
token -> ':' : {':', line_of('$1')}.
Erlang code.
value_of(Token) ->
    element(3, Token).
line_of(Token) ->
    element(2, Token).

注意

符号 '->' 和 ':' 必须以特殊方式处理，因为它们既是语法表示法的元符号，也是 Yecc 语法的终端符号。

5. lib/stdlib/src 目录中的 erl_parse.yrl 文件包含 Erlang 的语法。

注意

语法测试用于与某些规则关联的代码中，当测试失败时会抛出一个错误（并由生成的解析器捕获以产生错误消息）。通过调用 return_error(ErrorPosition, Message_string) 可以实现相同的效果，该函数在默认头文件 yeccpre.hrl 中定义。

文件

lib/parsetools/include/yeccpre.hrl

另请参阅

• Aho & Johnson: 'LR Parsing', ACM Computing Surveys, vol. 6:2, 1974。

• Kernighan & Pike: The UNIX programming environment, 1984。