Skip to content

Latest commit

 

History

History
93 lines (64 loc) · 3.38 KB

lalr.adoc

File metadata and controls

93 lines (64 loc) · 3.38 KB

理解 LALR 解析算法

由 Yecc 生成的语法解析器，使用了一种名为 LALR(Look-Ahead Left Reversed Rightmost Derivation) 的解析算法，即向前查看反向最右推导算法。

语法解析器使用 LALR 算法从左到右处理 Token 流，按照 Token 的顺序和格式匹配某条或多条语法规则。

语法解析器在确定匹配哪条语法规则时，需要向前查看。

LALR 工作机制

反向最右推导

Left := 语法解析器从左向右处理 Token 流。

Reversed Rightmost Derivation := 语法解析器自底向上地通过移进/规约匹配语法规则。

首先，语法解析器接收 Token 流;下一步，解析器把第一个 Token 向左移位，创建语法规则栈。

解析器处理一个 Token，会将 Token 压入栈中。

解析器使用栈来代替语法规则。实际上，解析器还会往栈里压入一些数字(状态, 记录 Token 匹配了哪些语法规则)，用来表示已经解析过了哪些语法规则。

下一步，解析器把下一个 Token 移位到栈中，解析器会检索与栈中 Token 匹配的语法规则。

如果语法规则匹配成功，解析器会使用语法规则替换栈中的 Token，称为`规约`。

解析器会检查可用的规则，在能规约的时候就规约，否则就在 Token 上应用语法规则。

向前查看

Look Ahead := 向前查看。

为了找到正确的匹配规则，解析器会先看下一个词条。

解析器还可以根据下一个 Token 和刚被解析过的语法规则，维护一张潜在匹配结果的状态表。

该表包含一系列的状态，用来描述当前哪些语法被解析过，以及应该如何根据下一个词条变更状态。

LALR 是一种复杂的 Token 流模式匹配状态机，使用 Yeec 生成 LALR解析器时，Yecc 会根据语法规则来计算状态表应该包含的内容。

LALR 语法解析器

Yecc 生成的 LALR 语法解析器代码分析。

构建

Makefile
Q := @

UNI_TOKENIZER := uni_tokenizer.erl
UNI_PARSER := uni_parser.erl

uni: $(UNI_TOKENIZER) $(UNI_PARSER)

$(UNI_TOKENIZER): uni_tokenizer.xrl
	$(Q) erlc -o $@ +'{verbose,true}' +'{report,true}' $<

$(UNI_PARSER): uni_parser.yrl
	$(Q) erlc -o $@ +'{verbose,true}' +'{report,true}' $<
unid:
	$(Q) rm -fr ebin/uni_*.beam
	$(Q) mkdir -p ebin
	$(Q) erlc +debug_info -o ebin $(UNI_TOKENIZER)
	$(Q) erlc +debug_info -o ebin $(UNI_PARSER)
	$(Q) erl -pa ebin

跟踪

$ make unid
> dbg:tracer().
> dbg:p(all, [c]).
> dbg:tpl({uni_parser, '_', '_'}, []).
> {ok, Tokens, _} = uni_tokenizer:string("").
> uni_parser:parse(Tokens).
(<0.81.0>) call uni_parser:parse([])
(<0.81.0>) call uni_parser:yeccpars0([],{no_func,no_location},0,[],[])
(<0.81.0>) call uni_parser:yeccpars1([],{no_func,no_location},0,[],[])
(<0.81.0>) call uni_parser:yecc_end(999999)
(<0.81.0>) call uni_parser:yeccpars2(0,'$end',[],[],{'$end',999999},[],{no_func,999999})
(<0.81.0>) call uni_parser:yeccpars2_0(0,'$end',[],[],{'$end',999999},[],{no_func,999999})
(<0.81.0>) call uni_parser:yeccerror({'$end',999999})
(<0.81.0>) call uni_parser:yecctoken_to_string({'$end',999999})
(<0.81.0>) call uni_parser:yecctoken2string({'$end',999999})
(<0.81.0>) call uni_parser:yecctoken2string1({'$end',999999})
(<0.81.0>) call uni_parser:yecctoken_location({'$end',999999})
{error,{999999,uni_parser,["syntax error before: ",[]]}}
> dbg:stop_clear().