从这个例子确定ķLR（k）的？ [英] Determining k of LR(k) from this example?

问题描述

我已经prepared下面的文法产生了C的逻辑和整数运算EX pressions一个子集：

I have prepared the following grammar that generates a subset of C logical and integer arithmetic expressions:

Expression:
    LogicalOrExpression
    LogicalOrExpression ? Expression : LogicalOrExpression

LogicalOrExpression:
    LogicalAndExpression
    LogicalOrExpression || LogicalAndExpression

LogicalAndExpression:
    EqualityExpression
    LogicalAndExpression && RelationalExpression

EqualityExpression:
    RelationalExpression
    EqualityExpression EqualityOperator RelationalExpression

EqualityOperator:
    ==
    !=

RelationalExpression:
    AdditiveExpression
    RelationalExpression RelationalOperator AdditiveExpression

RelationalOperator:
    <
    >
    <=
    >=

AdditiveExpression:
    MultiplicativeExpression
    AdditiveExpression AdditiveOperator MultiplicativeExpression

AdditiveOperator:
    +
    -

MultiplicativeExpression:
    UnaryExpression
    MultiplicativeExpression MultiplicativeOperator UnaryExpression

MultiplicativeOperator:
    *
    /
    %

UnaryExpression:
    PrimaryExpression
    UnaryOperator UnaryExpression

UnaryOperator:
    +
    -
    !

PrimaryExpression:
    BoolLiteral    // TERMINAL
    IntegerLiteral // TERMINAL
    Identifier     // TERMINAL
    ( Expression )

我想尝试利用移位/减少解析，因此想知道什么是最小的K（如果有的话），这些本语法是LR（K）？ （更一般如何确定从任意文法如果可能的话第k？）

I want to try using shift/reduce parsing and so would like to know what is the smallest k (if any) for which this grammar is LR(k)? (and more generally how to determine the k from an arbitrary grammar if possible?)

推荐答案

从唐纳德Knuths <一href="http://classes.engr.oregonstate.edu/eecs/winter2012/cs480/assignments/Knuth-1965-TranslationofLanguages.pdf"相对=nofollow>在语言的翻译从左至右，抽象，

From Donald Knuths On the Translation of Languages from Left to Right, in the abstract,

据表明，是否有语法问题是LR（K）的某个k 的是不可判定的，

It is shown that the problem of whether or not a grammar is LR(k) for some k is undecidable,

。换句话说，

给定一个文法G，∃k：GεLR（K）是不可判定的。

Given a grammar G, "∃k. G ∊ LR(k)" is undecidable.

因此，的，我们一般可以做的最好的就是尽量构建一个解析器LR（0），则LR（1），LR（2），等等。在某些时候，你一定会成功，或者你可能在某个时候放弃了当的 K 的变大。

Therefore, the best we can do in general is try constructing a parser for LR(0), then LR(1), LR(2), etc. At some point you will succeed, or you may at some point give up when k becomes large.

在这个特定的情况下，我碰巧知道你给的文法LALR（1），这意味着它因此必须LR（1）。我知道这是因为我写的LALR解析器类似的语言。它不能是LR（0），原因显而易见。（语法{A - > X，A - > A + X}不是LR（0））

In this specific case, I happen to know that the grammar you give is LALR(1), which means it must therefore be LR(1). I know this because I have written LALR parsers for similar languages. It can't be LR(0) for obvious reasons (the grammar {A -> x, A -> A + x} is not LR(0)).

这篇关于从这个例子确定ķLR（k）的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！