PEGJS：为谓词优先语法生成AST

Question

PEGJS：为谓词优先语法生成AST

javascriptparsinggrammarabstract-syntax-treepegjs

3

我回来重新探索PegJS，但很明显我还没有掌握核心概念。我正在尝试解析一个“查询语言”，它以谓词开始，然后是一系列操作数（其中可能包含另一个谓词）。所以一个简单的例子是：

OR(
   "string1"
   "string2"
)

I would like the above to be transformed into:

{
   predicate: "OR",
   operands: [
        {
           type: "STRING",
           value: "string1"
        },
        {
           type: "STRING",
           value: "string2"
        }
   ]
}

这个查询：

OR(
    "string1"
    "string2"
    AND (
        "string4"
        "string5"
    )
    "string3"
)

将会变成这个AST：

{
    predicate: "OR",
    operands: [
        {
            type: "STRING",
            value: "string1"
        },
        {
            type: "STRING",
            value: "string2"
        },
        {
            predicate: "AND"
            operands: [
                {
                    type: "STRING",
                    value: "string4"
                },
                {
                    type: "STRING",
                    value: "string5"
                }
            ]
        },
        {
            type: "STRING",
            value: "string3"
        }
    ] 
}

我的语法接近但有几个问题。这是当前的PEGJS语法。它可以直接粘贴到在线pegjs解析器中 (http://pegjs.majda.cz/online)。

start =
    or_predicate

or_predicate
  = ws* "OR" ws* "(" ws* operands:or_predicate ws* ")" ws* 
  { if(Array.isArray(operands)) {
      return {predicate: "OR", operands: operands} 
     } else {
      return {predicate: "OR", operands: [operands] }
     }
  }
  / and_predicate

and_predicate
  = ws* "AND" ws* "(" operands:and_predicate ")"
  { if(Array.isArray(operands)) {
      return {predicate: "AND", operands: operands} 
     } else {
      return {predicate: "AND", operands: [operands] }
     }
  }
  / operands  

operands
  = ws* values:operand+ { return values; }  

operand =
    string
    / ws or_predicate:or_predicate { return or_predicate; }

string =
   ws* "\"" value:valid_variable_characters "\"" 
   { return { type: "STRING", value: value.join("")}}

// List of valid characters for string variables
valid_variable_characters =
    [a-zA-Z0-9 _]+

ws =
   [ \t\n]

上述语法可以处理我提供的两个示例，但我注意到两个问题，这导致我有以下三个问题。

1. 这种简单的输入似乎会使语法失败（关键在于嵌套OR紧接在父OR之后，而“string”位于最后）：

OR(
   OR (
      "string1"
   )
   "string2"
)

我不确定是什么原因导致这个问题，也不知道如何解决。

2.目前语法中 operand 规则有一个奇怪的行：

operand =
    string
    / ws or_predicate:or_predicate { return or_predicate; }

请注意第三行在 or_predicate 之前的前导空格 (ws)。如果没有这个空格，我会得到错误信息“Maximum call stack size exceeded”。我认为这与左递归有关，但不确定。理想情况下，我希望在那里没有必需的 “ws”，所以像这样没有空格的查询可以工作:

OR("string1"OR("string2")"string3")

现在你需要人工添加一些额外的空格，就像这样：

OR("string1" OR("string2") "string3")

3. 我的语法分析方式是否完全错误？这是我尝试的第二个语法分析器，第一个是基于pegjs算术运算示例的，所以我意识到我可能完全走错了方向，这可能是我遇到问题的原因。

感谢您的帮助和时间！

最好的祝愿，

Ed

- Sarus

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dan · Accepted Answer

我对 PEG 也很陌生，但是主要通过查看示例而不是阅读文档来掌握它。

尝试将你的版本与此版本进行比较：

start
  = ws* predicate:predicate ws* { return predicate; }

predicate
  = "OR" ws* "(" operands:operand+ ")"  { return { predicate: 'OR', operands: operands }; }
  / "AND" ws* "(" operands:operand+ ")" { return { predicate: 'AND', operands: operands }; }

operand
  = ws* predicate:predicate ws* { return predicate; }
  / ws* string:string ws* { return string; }

string
  = "\"" chars:valid_variable_characters+ "\"" { return { type: "STRING", value: chars.join("")}}

valid_variable_characters = [a-zA-Z0-9 _]
ws = [ \t\n]

空格是可选的。

OR("str1"OR("str2""str3"AND("str4""str5"))"str6")

给：

{
   "predicate": "OR",
   "operands": [
      {
         "type": "STRING",
         "value": "str1"
      },
      {
         "predicate": "OR",
         "operands": [
            {
               "type": "STRING",
               "value": "str2"
            },
            {
               "type": "STRING",
               "value": "str3"
            },
            {
               "predicate": "AND",
               "operands": [
                  {
                     "type": "STRING",
                     "value": "str4"
                  },
                  {
                     "type": "STRING",
                     "value": "str5"
                  }
               ]
            }
         ]
      },
      {
         "type": "STRING",
         "value": "str6"
      }
   ]
}