1

我对词法分析器和解析器之间的任务分离有些困惑。

我正在尝试编写一个解析器，它采用 Perl 风格的正则表达式并构建一个语法树。我的问题是识别量词，例如{n,m}，这意味着前面的组或字符或字符类应该至少出现n，但不超过m次数。

关键是不完整/无效的量词例如{2,5asdf}不是量词，而是一组常规字符。

问题是：给定输入/a{2,5}/，词法分析器是否应该返回一个令牌列表，例如DELIMITER CHARACTER QUANTIFIER_START NUMBER COMMA NUMBER QUANTIFIER_END DELIMITER END（问题是QUANTIFIER_START可能不是量词的“真实”开始，取决于后面的内容），还是应该尝试匹配完整的quantifier 和 just return QUANTIFIER，这听起来更像是解析器的任务？

4

1 回答 1

1

使用将词法分析器和解析器分开的工具，通常在词法分析期间几乎没有空间让您更改标记。词法分析器通常独立于解析器运行，并且如果可能的话，使词法分析上下文敏感是 hacky（您可能想在谷歌上搜索PEG或无扫描仪解析，其中词法分析和解析之间没有真正的分离）。

但是，这完全取决于您使用的工具。我已经使用 ANTLR 创建了一个 PCRE 解析器，如果解析失败，它会使用回溯。因此，如果在解析后{2,5a无法构造量词（a无效），解析器将回溯到该字符并"{"从中生成一个LITERAL标记，然后继续。以一些 RAM 为代价，我启用了memoization ，导致解析器在大输入时仍然表现良好。

它解析X{2,5asdf}为：

'- ALTERNATIVE
   |- ELEMENT
   |  '- LITERAL='X'
   |- ELEMENT
   |  '- LITERAL='{'
   |- ELEMENT
   |  '- LITERAL='2'
   |- ELEMENT
   |  '- LITERAL=','
   |- ELEMENT
   |  '- LITERAL='5'
   |- ELEMENT
   |  '- LITERAL='a'
   |- ELEMENT
   |  '- LITERAL='s'
   |- ELEMENT
   |  '- LITERAL='d'
   |- ELEMENT
   |  '- LITERAL='f'
   '- ELEMENT
      '- LITERAL='}'

并且X{2,5}作为：

'- ALTERNATIVE
   '- ELEMENT
      |- LITERAL='X'
      '- QUANTIFIER
         |- NUMBER='2'
         |- NUMBER='5'
         '- GREEDY

您可以在此处使用解析器：http: //pcreparser.appspot.com/

ANTLR 语法可以在这里找到：https ://github.com/bkiers/PCREParser/blob/master/src/grammar/PCRE.g

于 2013-04-12T12:55:05.857 回答