递归下降解析器应该在重复的字母终端上出错

Question

主要问题：如何为命题逻辑（用 JavaScript 编写）更新我的递归下降解析器，以便像 "p~" 和 "pp" 这样的字符串将 return "Invalid" 消息？

我对 HTML、JavaScript 和解析还很陌生。我想看看我是否能够制作一个简单的网页，可以从命题逻辑中解析简单的公式。这是语法：

<formula> ::= <unaryconnective> <formula>
            | "(" <formula> <binaryconnective> <formula> ")"
            | <proposition>

<unaryconnective> ::= "~"

<binaryconnective> ::= "&"

<proposition> ::= "p"
                | "q"
                | "r"

我不熟悉编写这样的语法，所以希望这个语法是有意义的。据我了解维基百科关于左递归语法的内容，我不认为这种语法是左递归的，也不会出现歧义。

然后我尝试创建一个简单的网页，允许某人在文本框中输入公式，单击 "Validate" 按钮，然后 return 一条简单的消息说明公式是否有效.我试图编写一个可以进行解析的递归下降解析器。以下是我根据 Wikipedia、Stack Overflow 和我发现的与该主题相关的其他资源得出的结论 (jsfiddle)：

<!DOCTYPE html>
<html lang='en'>
  <head>
    <meta charset='UTF-8'>
    <title>Logic App</title>

    <script type="text/javascript">

    var sentence;
    var len;
    var i;
    var sym;

    function validate() {
      var result;

      sentence = document.getElementById('formulaentry').value;
      len = sentence.length;
      i = -1;

      if (sentence == "") {
        document.getElementById('formulaentry').value = "There's no formula!";
      } else {
        nextSym();
        result = formula();
        if(result == 0) {
          document.getElementById('formulaentry').value = "Invalid";
        } else {
        document.getElementById('formulaentry').value = "Valid";
        }
      }
    }

    function nextSym() {
      i++;
      if (i <= (len-1)) {
        sym = sentence.charAt(i);
      } else {
        sym = "";
      }
      //console.log("Current Sym:" + sym);
    }

    function accept(s) {
      if (sym == s) {
        nextSym();
        return 1;
      }
      return 0;
    }

    function expect(s) {
      if (accept(s)) {
        return 1;
      }
      return 0;
    }

    function formula() {
      if (unaryconn(sym)) {
        nextSym();
        if (formula() == 0) return 0;
        return 1;
      } else if (accept("(")) {
        if (formula() == 0) return 0;
        if (binaryconn(sym) == 0) return 0;
        nextSym();
        if (formula() == 0) return 0;
        if (!expect(")")) return 0;
        return 1;
      } else if (proposition(sym)) {
        nextSym();
        return 1;
      } else {
        return 0;
      }
    }

    function unaryconn(s) {
      if (s == "~") {
        return 1;
      } else {
        return 0;
      }

    }

    function binaryconn(s) {
      if (s == "&") {
        return 1;
      } else {
        return 0;
      }
    }

    function proposition(s) {
      if (s == "p" || s == "q" || s == "r") {
        return 1;
      } else {
        return 0;
      }
    }
    </script>
  </head>

  <body>
    <h1>Logic App</h1>

    <h2>Check if formula is well-formed:</h2>
    <p>Enter a formula into the text box and click "Validate" to see if it is a
    wff.</p>

    <form id='frmValidateFormula'>
      <p>
        <input
          type='text'
          id='formulaentry'
          placeholder='Input formula here'>
      </p>
      <p>
        <input
          type='button'
          id='btnValidate'
          value='Validate'
          onclick='validate()'>
      </p>
    </form>
  </body>
</html>

解析器似乎大部分都能正常工作。它正确地将以下字符串解析为有效公式：

p
~p
(p&p)
~(p&p)
(~(p&~~p)&(~p&~p))

但是，当这些字符串应该 return "Invalid":

时，它错误地 returns "Valid"

p~
pp
~p~
p&
p(
p)
ppqqpqpq

在这些情况下，解析器似乎不检查整个字符串，只检查第一个字母之前的字符和字母本身，因此认为没问题。我尝试在 "else if (proposition(sym)" 部分的 formula() 中添加某种验证，以确保字母后面的字符是有效字符，但这不起作用，因为有效字符会根据其前面的内容而变化。改变我的语法可能会有帮助。我真的不明白在创建这些语法时我应该考虑什么，除了左递归会给递归下降解析器带来麻烦。我在 Stack Overflow 上查看了几个关于递归下降解析器的问题，但 none 似乎对我的问题有所帮助。

我如何更新我的解析器，以便得到这样的字符串 return "Invalid"？我不一定要寻找完整的答案，只是寻找一些关于要考虑的事情或要查看的资源的指示。如果您还知道在构建语法时要考虑什么的好资源（尤其是参考解析器），那就太棒了。

注意：我的解析器目前不处理空格。我现在很好，因为我主要关心的是在更新内容以处理空白之前让其他解析正确。

Answer 1

我还没有深入研究你的代码，但这是我的印象：

您的解析器正在检查它看到的第一组字符是否构成有效的公式，然后停止。如果之后出现垃圾，没关系，您的解析器仍然很高兴，因为它找到了有效的公式。

我在你的语法中看到了两种处理它的方法：

要求公式以某些 "end of stream" 元字符结尾
添加匹配一系列公式的新规则。例如

<document> ::= <formula> |
               <formula> <document>

（当然，这是左递归的，但你应该可以轻松解决这个问题。）

还有：

} else if (proposition(sym)) {
    nextSym();
}

我怀疑这个分支没有 return 任何东西。

递归下降解析器应该在重复的字母终端上出错

Recursive Descent Parser Should Error on Repetitive Letter Terminals

javascript

parsing

recursive-descent

propositional-calculus