gpt4 book ai didi

parsing - 乔姆斯基层次结构和 LL(*) 解析器

转载 作者:行者123 更新时间:2023-12-01 18:16:14 27 4
gpt4 key购买 nike

我想解析一种编程语言。我读了很多关于形式语言、乔姆斯基层次结构和 ANTLR 的内容。但我找不到有关如何将 ANTLR v3 作为 LL(*) 递归下降解析器接受的语言与乔姆斯基层次结构相关联的信息。

乔姆斯基类型如何与 LL(*) 混合?非常感谢任何信息(在线、书籍、论文)。

编辑:ANTLR 的句法/语义谓词和回溯如何映射到此?

最佳答案

乔姆斯基层次结构基本上是:

  1. 常规语言
  2. 上下文无关语法
  3. 上下文相关语法
  4. 递归可枚举(图灵完备)语法

LL 语法(和解析器)是上下文无关语法的子集。使用它们是因为常规语言对于编程目的太弱,并且一般的上下文无关解析器的时间复杂度为 O(n^3),这对于解析程序来说太慢。事实上,用辅助函数增强解析器确实会使其变得更强大。 The Wikipedia entry on LL parsers解释了其中的一些内容。 The Dragon Book被认为是编译器方面的领先教科书,并且可以进一步解释。

关于parsing - 乔姆斯基层次结构和 LL(*) 解析器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/442325/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com