JavaScript 语法部分的左因式分解

Question

我使用 EcmaScript 5.1 表达式的语法：

PrimaryExpression :
    this
    Identifier
    Literal
    ArrayLiteral
    ObjectLiteral
    ( Expression )

FunctionExpression :
    function Identifieropt ( FormalParameterListopt ) { FunctionBody }

MemberExpression :
    PrimaryExpression
    FunctionExpression
    MemberExpression [ Expression ]
    MemberExpression . IdentifierName
    new MemberExpression Arguments

NewExpression :
    MemberExpression
    new NewExpression

CallExpression :
    MemberExpression Arguments
    CallExpression Arguments
    CallExpression [ Expression ]
    CallExpression . IdentifierName
Arguments :
    ( )
    ( ArgumentList )

LeftHandSideExpression :
    NewExpression
    CallExpression

我用 Wirth 表示法重写它，为它编写递归解析器。我得到了什么：

PrimaryExpression = this | Identifier | Literal | ObjectLiteral | "(" ExpressionNoIn ")"

Literal = NullLiteral | BooleanLiteral | NumericLiteral | StringLiteral 

ObjectLiteral = "{" [PropertyNamesAndValues] "}"

MemberExpression = ( PrimaryExpression | FunctionExpression | new MemberExpression Arguments ) MemberExpression'    

MemberExpression' = ( "." Identifier | "[" Expression "]" ) MemberExpression' | e.

NewExpression = ( PrimaryExpression | FunctionExpression ) MemberExpression' | new NewExpression'   

NewExpression' = MemberExpression Arguments MemberExpression' | NewExpression                           

CallExpression = MemberExpression Arguments CallExpression'

CallExpression' = ( Arguments | "[" Expression "]" | "." Identifier ) CallExpression' | e.

Arguments = "(" [ArgumentList] ")"

LeftHandSideExpression = NewExpression | CallExpression

所以，问题是如何在我的新语法中对规则 LeftHandSideExpression 使用左因子分解。我需要它，因为 First[LeftHandSideExpression] 和 First[CallExpression] 的交集不为空。

谢谢！

Answer 1

基本思想是避免在 2 个产生式和路径共享一个公共标记的解析中做出决定。所以基本上，如果终端被埋在其他非终端中并共享，你想将终端移到产品的前面。

基本上，您会想要分解出常见的标记，并将它们放在新的非终结符中以避免非确定性选择。

例如：如果我有这个语法：

S -> X | Y
X -> ab
Y -> ac

我必须 "move" 终端 "a" 启动，这样解析器在尝试选择是接受 X 还是 Y 时就不会卡住。

解决方案如下：

S -> A'
A' -> a(X|Y)
X -> b
Y -> c

请仔细考虑之前可能采用的所有路径，包括 lambda（空字符串）。处理 lambda 是一种特殊情况，需要进一步处理才能获得合适的语法（或者甚至反映您想要的语言的语法）。

虽然是的，这增加了额外的非终结符，但它是一种算法，可以保证不需要前瞻的确定性语法。

注意：一些语言生成器（解析语法）可以用先行值指定。有时为了简单起见，这是首选，但请注意，使用超过 1 的前瞻性将大大增加将包含在解析器中的前瞻性 table。它是 N^k 的顺序，其中 n 是产品的数量，k 是先行。

该站点使用我在编译器中使用的特定形式对其进行了解释 class： http://www.cs.sun.ac.za/rw711/2012term2/lectures/lec5/l5.pdf

如果不喜欢外部站点链接，我可以拍摄一些幻灯片的图像并将它们附加在此处以供将来存档。

我建议您阅读语法，因为它们会很有趣！

JavaScript 语法部分的左因式分解

Left factoring of part of JavaScript grammar

javascript

compiler-construction

recursion

grammar

parsing