0

细绳：

ab/c*efg*h/+d-+

后缀语法：

<postfix> = <identifier> | <postfix><postfix><operator>
<operator> = + | - | * | /
<identifier> = a | b | ... | z

问题：

上面的字符串是有效的后缀表达式吗？用 GRAMMAR FOR POSTFIX 表达式来解释。

不，这不是评分作业。是的，这是来自一本书。我正在寻找问题的概念性答案，不一定是代码。如何查看语法并评估字符串是否匹配？

4

1 回答 1

1

如何查看语法并评估字符串是否匹配？

换句话说，“我如何使用语法解析字符串？”，对吧？

最简单的方法是使用 oracle 解析器；也就是说，一个解析器可以只咨询一个预言机并决定减少哪个生产。

解析是推导的逆过程。如果我们可以从开始符号导出字符串，那么我们可以反转过程以从字符串构造解析树。手边有一个可靠的预言机可以很容易地进行任何一种方式。所以让我们产生最右边的推导。回想一下，在最右边的推导中，总是最右边的非终结符被扩展。

（为了简洁起见，我将非终结符表示为大写字母 P、O 和 I。我还将字符串右对齐，以便您可以更轻松地看到“对应字符”是什么。）：

              P   P => P P O
            PPO   O => +
            PP+   P => P P O
          PPPO+   O => -
          PPP-+   P => I
          PPI-+   I => d
          PPd-+   P => P P O
        PPPOd-+   O => +
        PPP+d-+   P => P P O
      PPPPO+d-+   O => /
      PPPP/+d-+   P => I
      PPPI/+d-+   I => h
      PPPh/+d-+   P => P P O
    PPPPOh/+d-+   O => *
    PPPP*h/+d-+   P => I
    PPPI*h/+d-+   I => g
    PPPg*h/+d-+   P => I
    PPIg*h/+d-+   I => f
    PPfg*h/+d-+   P => I
    PIfg*h/+d-+   I => e
    Pefg*h/+d-+   P => P P O
  PPOefg*h/+d-+   O => *
  PP*efg*h/+d-+   P => I
  PI*efg*h/+d-+   I => c
  Pc*efg*h/+d-+   P => P P O
PPOc*efg*h/+d-+   O => /
PP/c*efg*h/+d-+   P => I
PI/c*efg*h/+d-+   I => b
Pb/c*efg*h/+d-+   P => I
Ib/c*efg*h/+d-+   I => a
ab/c*efg*h/+d-+

那么，神谕是如何弄清楚要说什么的呢？好吧，如果最右边的非终结符是<operator>or <identifier>，它只需要看一下目标字符串的对应字符，看看扩展是什么。如果最右边的非终结符是<postfix>，那么有两种可能性：<postfix> => <postfix> <postfix> <operator>和<postfix> => <identifier>。然后目标字符串的相应字符将与<operator>the<identifier>或非终结符对齐，因此很容易知道两种可能的产生中的哪一种能够继续。这正是我产生推导的方式，使用一个小型 Lua 程序作为我的预言机。

现在，如果我们真的需要继续前进，从字符串开始并以单个非终结符结束，会发生什么<postfix>？好吧，我们只需要逆转我们的步骤。如果我们正在查看一个字母，我们将需要从 派生它<identifier>，然后立即从 派生该标识符<postfix>。如果我们正在查看一个运算符，我们需要从 导出它<operator>，然后立即将最后两个<postfix>加上运算符导出到一个 new <postfix>。

够概念吗？

于 2013-10-21T02:26:46.177 回答