(E)BNF如何匹配到下一个非终结规则？

Question

我正在尝试为 RIS格式的内容撰写语法，使用 nearley。

文件示例：

TY  - JOUR
KW  - foo
KW  - bar
ER  - 

一个 *.ris 文件总是以标签 TY 开始，以标签 ER 结束。中间可以有很多其他的标签，比如 KW（关键词）。

规范说明单个 KW 语句可以跨越多行。

因此，下面这个例子：

TY  - JOUR
KW  - foo
bar
baz
KW  - bat
ER  - 

等同于：

TY  - JOUR
KW  - foo bar baz
KW  - bat
ER  - 

我正在努力想出一个语法，大致意思是：

关键字以KW开头，后跟 -，然后是：

• 直到行尾的字母
• 直到下一个关键字之前的所有字母

无论我尝试什么，都会“吞噬”其他语句，例如第一个多行关键字捕获其后的所有内容。 你会如何编写这个规则？ 我不一定需要 nearley 的具体答案。任何能引发我的“恍然大悟”的东西都可以！

- customcommander

Answer 1

我肯定不擅长设计语法（您可能已经发现了），但这引发了我的“噢”的时刻：

很多人指出，为nearley编写语法很难。事实上，总的来说，编写语法非常困难。某些与语法相关的问题是可证明不可判定的，这并没有帮助。

请参见https://nearley.js.org/docs/how-to-grammar-good 并且：

使用分词器有许多好处。它可以...

...通常使您的解析器速度提高一个数量级以上。

...允许您编写更清晰、更易于维护的语法。

...在某些情况下有助于避免歧义的语法。[...]

请参见https://nearley.js.org/docs/tokenizers 我知道nearley推荐使用moo-lexer：

nearley支持并推荐Moo，一个超快的词法分析器。

请参见https://nearley.js.org/docs/tokenizers 所以我在谷歌上搜索，找到了这个令人惊叹的YouTube教程，它确实解决了我的问题。非常感谢@airportyh！

起初，我认为这对我的用例来说太复杂了，但结果证明，使用词法分析器既可能又简单！

---

为了简化起见，我将提供一个带有截断的RIS文件的解决方案：

sample.ris

KW  - foo
bar
baz
KW  - bat

这个文件在解析后应该返回['foo bar baz', 'bat']。 首先，让我们安装一些东西。

yarn add nearley
yarn add moo

现在让我们定义我们的词法分析器。

lexer.js

const moo = require('moo');

const lexer =
  moo.compile
    ( { NL: {match: /[\n]/, lineBreaks: true}
      , KW: 'KW'
      , SEPARATOR: "  - "
      , CONTENT: /[a-z]+/
      }
    );

module.exports = lexer;

我们定义了四个标记：

1. 换行符 NL
2. KW 关键字 ... 关键字！
3. SEPARATOR：标签和其内容之间的分隔符
4. 标签的CONTENT

接下来，让我们定义我们的语法。

grammar.ne

@{% const lexer = require('./lexer.js'); %}
@lexer lexer
@builtin "whitespace.ne"

RECORD -> _ KW:+                {% ([, keywords]) => [].concat(...keywords) %}
KW     -> %KW %SEPARATOR LINE:+ {% ([,,lines])    => lines.join(' ')        %}
LINE   -> %CONTENT __           {% ([{value}])    => value                  %}

注意：看看我们如何通过在词法分析器中添加前缀%来引用定义的令牌！

现在我们需要编译我们的语法。

Nearley附带了一个编译器：

yarn -s nearleyc grammar.ne > grammar.js

你也可以在 package.json 中定义一个 compile 脚本：

{

  ...

  "scripts": {
    "compile": "nearleyc grammar.ne > grammar.js",
  }

  ...

}

最后，让我们构建一个解析器并使用它！

const nearley = require('nearley');
const grammar = require('./grammar.js');

module.exports =
  str => {
    const parser = new nearley.Parser(nearley.Grammar.fromCompiled(grammar));
    parser.feed(str);
    return parser.results[0];
  };

注意：这需要已编译的语法，即grammar.js

让我们向它输入一些文本：

const parser = require('./parser.js');

parser(`
KW  - foo
bar
baz
KW  - bat
`);
//=> [ 'foo bar baz', 'bat' ]

最后一条提示：您还可以使用nearley-test测试您的语法：

cat sample.ris | yarn -s nearley-test -- -q grammar.js

- customcommander