我想知道在解析过程中应用单个产生式规则的结果是否有一个约定的名称?
假设我的语法有这样的产生式:
attr -> NAME, EQUAL, TEXT
然后在解析过程中,我匹配该产生式并获得一小部分代表替换/匹配的数据:
((NAME, 'foo'), (EQUAL, '='), (TEXT, 'bar'))
惯例规定它的名称是什么?到目前为止我收集的候选人是:
- 生产 - 我不喜欢这个选项,因为尽管这些项目是通过应用规则“生产”的,但“attr -> NAME, EQUAL, TEXT”位已经存在对该术语的合法主张。
- 部分推导——我更喜欢一个单词,但这对我来说很有意义,因为整个解析结果是一个推导,而这是该推导的一个“原子”或步骤。里>
- 替换——我有点喜欢这个,但是看起来有点通用。
除了完全阐明解决方案域的强烈愿望之外,采用产生式规则并返回匹配标记(和/或解析的非终结符)的函数(可能是 match(rule, tokens)
)需要为其返回的内容提供一个名称(或者至少它的调用者是这样的)。
无论如何,下一步是使用这些值在抽象语法树 (AST) 中生成一个节点,但该节点是一个单独的对象,具有可能不同的形式和附加字段。
在解析和编译器术语方面具有更广泛经验的人是否知道适合于此的术语?
最佳答案
在自下而上的解析(例如,LALR)中,对一个或多个产生式规则的部分的识别是通过构建复杂的 FSA 来有效完成的,其中状态本质上对哪些产生式可能与在某个点上所看到的相匹配进行编码。输入。词汇:
处理 token 并在匹配部分(多个)生产中取得单位进展的行为称为转移(它是 FSA 中的转换,加上记录在转换已发生的解析堆栈)
在到达(通过移动一次或多次)某个产生式的明显结尾后,解析器将执行一个(或多个)归约,其中每一个都表示对一个产生式的识别。生产。对于长度为 L 的特定产生式规则 R 的每次归约,都会从解析堆栈中弹出 L 个条目,以确定归约后 FSA 的状态。然后,解析器尝试转移产生式左侧的标记。
您似乎有兴趣命名准备进行减少的状态。我没有见过用来命名此状态的术语,但我认为可还原是一个合理的术语。
(处于可简化状态的 LALR 解析器中实际发生的情况是,根据 [特定于状态的] 前瞻集检查下一个[尚未移动的] 输入标记,前瞻产生式,看看人们是否真的可以在归约中使用产生式。[实际上,这是检查产生式在其发现的上下文中是否有效。]如果可以,则进行归约;如果不能,那么产生式实际上并不适用并被忽略;在这种情况下,最好对前瞻标记进行有效的移位)。
关于parsing - 应用单一生产规则的产品的常见说法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28894058/