yecc

yecc

模块

yecc

模块摘要

LALR-1分析器发生器

描述

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

为了理解本文，您还必须查看yaccUNIX（TM）手册中的文档。为了理解解析器生成器的概念以及有限预见的LALR解析的原理和问题，这很可能是必需的。

输出

file(Grammarfile [, Options]) -> YeccRet

类型

Grammarfile声明和语法规则的文件。回报ok一旦成功，或error如果有错误。如果没有错误，将创建包含解析器的Erlang文件。备选方案如下：

{parserfile，Parserfile} **。 Parserfile是将包含生成的Erlang分析器代码的文件的名称。 缺省值（“”）是将扩展名.erl添加到除去.yrl扩展名的Grammarfile。 {includefile，Includefile} **。 指示用户可能想要使用的自定义序言文件，而不是默认文件lib / parsetools / include / yeccpre.hrl，否则这些文件将包含在生成的解析器文件的开头。注： Includefile在解析器文件中是“按原样”包含的，所以它不能有自己的模块声明，也不应该编译它。 但是，它必须包含必要的出口声明。 默认由“”指示。 {report_errors，bool（）} **。 导致错误在发生时被打印。 默认值是true。 {report_warnings，bool（）} **。 导致警告在发生时被打印。 默认值是true。 {report，bool（）} **。 这是report_errors和report_warnings的简写形式。warnings_as_errors**

导致将警告视为错误。

{return_errors，bool（）} **。 如果设置了该标志，则在出现错误时返回{错误，错误，警告}。 默认为false。 {return_warnings，bool（）} **。 如果设置了此标志，则会向成功返回的元组添加一个包含警告的额外字段。 默认为false。 {return，bool（）} **。 这是return_errors和return_warnings的简写形式。 {verbose，bool（）} **。 确定解析器生成器是否应提供有关已解析和未解析的解析操作冲突的完整信息（true），还是仅针对阻止从输入语法生成解析器的冲突（false，默认值）。

任何布尔选项都可以设置为true通过声明选项的名称。例如，verbose等于{verbose, true}...

Yecc使用Parserfile剥离.erl扩展名的选项的值作为生成的解析器文件的模块名称。

Yecc将添加扩展.yrl到Grammarfile名，扩展名.hrl的Includefile名称，并扩展.erl到Parserfile名称，除非扩展已经存在。

format_error(Reason) -> Chars

类型

返回由返回的错误元组的英文描述性字符串yecc:file/1,2。该函数主要由调用Yecc的编译器使用。

预处理

scanner预处理要分析的文本（程序等）不在yecc模块中提供。扫描仪作为一种词典查找程序。编写只使用字符标记作为终端符号的语法是可能的，从而消除了扫描器的需要，但这会使解析器变得越来越大和越来越慢。

用户应该实现一个扫描程序来分割输入文本，并将其转换为一个或多个令牌列表。每个标记应该是一个元组，包含关于句法分类，文本中的位置（例如行号）以及文本中找到的实际终端符号的信息：{Category, LineNumber, Symbol}。

如果终端符号是类别的唯一成员，并且符号名称与类别名称相同，则令牌格式可能是{Symbol, LineNumber}。

扫描器生成的令牌列表应以end_of_input解析器正在查找的特殊元组结束。这个元组的格式应该是{Endsymbol, LastLineNumber}，其中Endsymbol的一个标识符与语法规则的所有终端和非终端类别相区分。该Endsymbol可以在语法文件（见下文）中声明。

最简单的情况是将输入字符串分割成标识符列表（原子），并将这些原子用作标记的类别和值。例如，输入字符串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解析器解析语法文件之前标记语法文件。 扫描仪实现的更一般方法是使用扫描仪生成器。 Erlang名为leex的扫描仪生成器正在开发中。

语法定义格式

在语法文件中允许comments以a开头的Erlang风格'%'。

每个declaration或rule以点（字符'.'）结尾。

语法以可选header部分开始。在模块声明之前，标题首先放置在生成的文件中。标题的目的是为了让EDoc生成的文档更好看。每个标题行应用双引号括起来，并在行之间插入换行符。例如：

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

接下来是nonterminal categories在规则中使用的声明。例如：

Nonterminals sentence nounphrase verbphrase.    

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

接下来是一个声明terminal categories，它是由扫描器产生的令牌类别。例如：

Terminals article adjective noun verb.    

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

接下来是一个声明rootsymbol，或语法的起始类别。例如：

Rootsymbol sentence.    

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

在根符号声明之后是end_of_input您的扫描器将使用的符号。例如：

Endsymbol '$end'.    

接下来是一个或多个声明operator precedences，如果需要的话。这些用于解决移位/减少冲突（参见yacc文档）。

操作符声明示例：

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

这些声明意味着'='被定义为具有优先权100的右联合二元运算符，'=='和'= / ='是不具有关联性的运算符，'+'和'*'是左联合二元运算符， *'优先于'+'（正常情况），而' - '是优先级高于'*'的一元运算符。 '=='不具有关联性的事实意味着像== == c这样的表达式被认为是语法错误。

某些规则会被分配优先级：每个规则都会从规则右侧提到的最后一个终端符号中获得优先级。也可以声明非终端的优先级，即“上一级”。当操作员超载时这是实用的（参见下面的例子3）。

接下来是grammar rules.每条规则都有一般形式

Left_hand_side -> Right_hand_side : Associated_code.    

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

符号，例如'{'，'.'等等，具有如在语法规则终端或非末端符号使用时，被封闭在单引号。使用该标志的'$empty'，'$end'以及'$undefined'应该避免。

语法文件的最后一部分是Erlang代码（=函数定义）的可选部分，它在结果解析器文件中“按原样”包含。本节必须以伪声明或关键词开始

Erlang code.    

本节后面没有语法规则定义或其他声明。为避免与内部变量发生冲突，请勿使用本节Erlang代码中以两个下划线字符（'__'）开头的变量名，或与单个语法规则关联的代码中使用变量名。

可选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}}}    

相关联的代码包含pseudo variables '$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有关使用运算符优先级的文档。

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

myparser:parse(myscanner:scan(Inport))    

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

使用标准的序言，此调用将返回{ok, Result}，在哪里Result是语法文件的Erlang代码构建的结构，或者{error, {Line_number, 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, Endline}
{eof, Endline}
{error, Error_description, Endline}    

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

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

更多的例子

• 用于将中缀算术表达式解析为前缀记号的语法，无需操作符优先级：非终结符ET F.终端'+''*''（''）'编号。Rootsymbol E. E - > E'+'T：{'$ 2'，'$ 1'，'$ 3'}。E - > T：'$ 1'。T - > T'*'F：{'$ 2'，'$ 1'，'$ 3'}。T - > F：'$ 1'。F - >'（'E'）'：'$ 2'。F - >号码：'$ 1'。

• 与运算符优先级相同的情况变得更简单：

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'.    

• 重载减号运算符：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.

• 用于解析语法文件(包括其本身)的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文法的终端符号。

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

注

在与某些规则相关的代码中使用语法测试，并在测试失败时引发错误（并由生成的解析器捕获以产生错误消息）。使用缺省头文件中return_error(Error_line, Message_string)定义的调用可以实现同样的效果yeccpre.hrl。

档案

lib/parsetools/include/yeccpre.hrl    

另见

Aho＆Johnson：“LR解析”，ACM Computing Surveys，vol。6：2，1974。