为最左和最右推导导出字符串“abb”

问题

让我们考虑使用 LMD 和 RMD 导出“abb”字符串的语法

   S->AB/ε

   A-> aB

   B-> 锑

解决方案

我们必须使用上下文无关语法。

派生是一系列产生式规则，用于获取输入字符串。

在解析过程中，我们必须做出两个决定，如下所示 -

• 我们必须决定必须更换哪个非终端。

• 我们必须决定使用哪个产生式规则替换哪个非终结符。

有两个选项可以决定哪个非终端必须用产生式规则替换 -

• 最左推导

• 最右推导

最左推导

从左到右扫描输入并替换为生产规则。

The given production rules are:
   S->AB/ ε
   A-> aB
   B-> Sb
Let’s derive the string “abb” using LMD
   S->AB
   ->aBB {A->aB}
   ->aSbB {B->Sb}
   ->abB {S-> ε}
   ->abSb {B->Sb}
   ->abb {S-> ε}
Which is our final string

最右推导

从右到左扫描输入并用产生式规则替换。

The given production rules are:
   S->AB/ ε
   A-> aB
   B-> Sb
Let’s derive the string “abb” using RMD
   S -> AB
   ->ASb {B->Sb}
   ->Ab {S-> ε}
   ->aBb {A->aB}
   ->aSbb {B->Sb}
   ->abb {S-> ε}
Reached our final string