zxh0/luago-book

16.4 表达式文法产生式EBNF有误

King19931229 opened this issue · 3 comments

原文法:

exp   ::= exp12
exp12 ::= exp11 {or exp11}
exp11 ::= exp10 {and exp10}
exp10 ::= exp9 {(‘<’ | ‘>’ | ‘<=’ | ‘>=’ | ‘~=’ | ‘==’) exp9}
exp9  ::= exp8 {‘|’ exp8}
exp8  ::= exp7 {‘~’ exp7}
exp7  ::= exp6 {‘&’ exp6}
exp6  ::= exp5 {(‘<<’ | ‘>>’) exp5}
exp5  ::= exp4 {‘..’ exp4}
exp4  ::= exp3 {(‘+’ | ‘-’) exp3}
exp3  ::= exp2 {(‘*’ | ‘/’ | ‘//’ | ‘%’) exp2}
exp2  ::= {(‘not’ | ‘#’ | ‘-’ | ‘~’)} exp1
exp1  ::= exp0 {‘^’ exp2}
exp0  ::= nil | false | true | Numeral | LiteralString
		| ‘...’ | functiondef | prefixexp | tableconstructor

这里的文法 + - * / or and 这些是没有处理左结合的,..没有处理右结合
虽然实现的代码上处理了
符合编译原理的文法应该是这样的

exp ::= exp12
exp12 ::= (exp12 or exp 11) | exp11
exp11 ::= (exp11 and exp10) | exp10
......
省略
......
exp5 ::= exp4 {'..' exp5}

消除左递归形式:
@表示空产生式(ε)

exp12 ::= exp11 exp12'
exp12' ::= (or exp11 exp12') | @
exp11 ::= exp10 exp11'
exp11' ::= (and exp10 exp11') | @
......
省略
......
exp5 ::= exp4 {'..' exp5}

由于exp12'与exp11'这些尾项产生式都是尾递归
因此可以使用书中的循环进行优化

func parseExp12(lexer *Lexer) Exp {
	exp := parseExp11(lexer)
	for lexer.LookAhead() == TOKEN_OP_OR {
		line, op, _ := lexer.NextToken()
		lor := &BinopExp{line, op, exp, parseExp11(lexer)}
		exp = optimizeLogicalOr(lor)
	}
	return exp
}

exp5相当于原地展开递归

func parseExp5(lexer *Lexer) Exp {
	exp := parseExp4(lexer)
	if lexer.LookAhead() != TOKEN_OP_CONCAT {
		return exp
	}

	line := 0
	exps := []Exp{exp}
	for lexer.LookAhead() == TOKEN_OP_CONCAT {
		line, _, _ = lexer.NextToken()
		exps = append(exps, parseExp4(lexer))
	}
	return &ConcatExp{line, exps}
}

书的EBNF有误导成分

zxh0 commented

收到,会在第二版改进。

zxh0 commented

感谢提供反馈😊

感谢提供反馈😊

我也是简单找到个错,大神的书才是经典😄