为什么词法分析和语法分析应该分开

主要观点:对于大语言/解析器,用快速算法处理简单事,用慢速算法处理复杂事,且词法分析和语法分析是不同的事。
关键信息:

  • 词法分析识别语言的非递归结构,输出令牌流;语法分析识别语言的递归结构,输出树。
  • 词法分析较简单且稳定,而语法分析模型不明确且更复杂。如 Rust 早期改变解析模型,CPython 从 pgen LL(1) 转为 PEG 等。
  • 分离词法分析和语法分析可降低 O(n^3) 中的 n,提高性能,如 Sixty 编译器和 ShellCheck 的案例。
  • 模态词法分析器更利于子语言的组合,如 OSH 利用词法分析模式。
  • 调试大型语法的 PEG 较困难,因词法和语法交织;而 IDE 支持倾向于分离词法分析。
  • 词法分析可轻松处理位置信息,IDE 中如 Raku 的 IntelliJ 平台就分离了词法和语法。
    重要细节:
  • 词法分析用正则语言可在 O(n) 时间和 O(1) 空间完成,有基本算法;语法分析 CFG 一般为 O(n^3),PEG 需 O(n) 空间或指数时间。
  • 有多个关于词法和语法分离的讨论线程及相关观点,如某些语言创建工具的讨论等。
  • 提到 Perl6 的相关事件认为不应拆分语言实现的传统阶段。
阅读 16
0 条评论