1

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

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

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

<unaryconnective> ::= "~"

<binaryconnective> ::= "&"

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

我是这样写语法的新手，所以希望这种语法有意义。据我了解维基百科对左递归语法的了解，我不相信这种语法是左递归的，也不显得模棱两可。

然后我尝试创建一个简单的网页，允许某人在文本框中输入公式，单击“验证”按钮，并返回一条简单的消息，说明公式是否有效。我试图编写一个可以进行解析的递归下降解析器。以下是我根据 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))

但是，当它应该返回“无效”时，它错误地为这些字符串返回“有效”：

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

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

如何更新我的解析器，以便此类字符串返回“无效”作为结果？我不一定要寻找完整的答案，只是一些关于要考虑的事情或要查看的资源的指示。如果您还知道构建语法（尤其是参考解析器）时要考虑的内容的好资源，那将是非常棒的。

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

4

1 回答 1

2

我没有太彻底地研究你的代码，但这是我的印象：

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

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

  • 要求公式以一些“流结束”元字符结尾

  • 添加与一系列公式匹配的新规则。例如

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

（当然，这是左递归的，但您应该能够轻松解决这个问题。）

还：

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

我觉得这个分支没有返回任何东西很可疑。

于 2019-03-07T20:14:32.503 回答