当前位置: 动力学知识库 > 问答 > 编程问答 >

parsing - What is the right way to convert EBNF to BNF when using GLR parser?

问题描述:

EBNF like this

Goal = Stmt

Stmt = "if" "expr" "then" Stmt ("else" Stmt)?

Stmt = "S"

Should I Convert this to

Goal = Stmt

X = "else" Stmt

Stmt = "if" "expr" "then" Stmt | "if" "expr" "then" Stmt X

Stmt = "S"

Or

Goal = Stmt

Stmt = "if" "expr" "then" Stmt | "if" "expr" "then" Stmt "else" Stmt

Stmt = "S"

Are these two BNF mean the same to GLR parser?

------------------------ APPEND CONTENT ------------------------------

If the lexes are

"if" "expr" "then" "if" "expr" "then" "S" "else" "S"

GLR parser should get two trees

Goal

Stmt

"if"

"expr"

"then"

Stmt

"if"

"expr"

"then"

Stmt

"S"

"else"

Stmt

"S"

And

Goal

Stmt

"if"

"expr"

"then"

Stmt

"if"

"expr"

"then"

Stmt

"S"

"else"

Stmt

"S"

But the first converted BNF can only get the first tree, because when it meet "else", there is no conflict in reduce/shift, the conflict is at meeting X.

The second BNF will has a reduce/shift conflict when it meet "else", so the parser will split to two threads to parse in different conditions.

Am I right? Is there any ACTION, GOTO TABLE generator that will treat the first BNF just like the second one?

网友答案:

They are equivalent grammars and will parse the same language.

Your grammar with X only uses X in one place. The net effect is as if the body of X was substituted where X is referenced. In practice, having the X production will force the parser to do a bit more work. Unless you want to attach a semantic action to the reduction for X, that additional work isn't buying anything in efficiency.

To the extent that having such use-once production makes the grammar more maintainable, this is useful to do. In a small grammar like this, I don't see the point. In practical grammars (we have a GLR grammar for IBM COBOL with 5000 productions [blame IBM, not us]), such structuring can be pretty helpful and the additional parsing overhead doesn't matter.

分享给朋友:
您可能感兴趣的文章:
随机阅读: