语法解析中的 LR parse 与 LL Parse

[ilife5]

L的意思为读输入字符时遵循固定的方向，通常是单行内从左向右，多行从上向下。而R或者L的意思则是构建语法树的模式是从最右推导还是最左推导。

下面举例演示最右推导以及最左推导：

语法如下

 (1)  S → S + S
 (2)  S → 1
 (3)  S → a

输入字符为

1 + 1 + a

[ilife5]

最右推导：

S → S + S (1)
   → S + a (3)
   → S + S + a (1)
   → S + 1 + a (2)
   → 1 + 1 + a (2)

构建出来的语法树如下：

           S 
          /|\
         / | \
        /  |  \
       S  '+'  S
      /|\      |
     / | \     |
    S '+' S   'a'
    |     |
   '1'   '1'

[ilife5]

最左推导：

S → S + S (1)
   → 1 + S (2)
   → 1 + S + S (1)
   → 1 + 1 + S (2)
   → 1 + 1 + a (3)

构建出来的语法树如下：

           S
          /|\
         / | \
        /  |  \
       S  '+'  S
       |      /|\
       |     / | \
      '1'   S '+' S
            |     |
           '1'   'a'