Ordered Context-Free Grammars Revisited

被引：0

作者：

van der Merwe, Brink ^{[1
]}

机构：

[1] Stellenbosch Univ, Dept Comp Sci, Stellenbosch, South Africa

来源：

ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE | 2023年 / 388卷

关键词：

Ordered context-free grammars; Unambiguous grammar formalisms; Shared packed parse forests; EXPRESSION; POWER;

D O I：

10.4204/EPTCS.388.13

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We continue our study of ordered context-free grammars, a grammar formalism that places an order on the parse trees produced by the corresponding context-free grammar. In particular, we simplify our previous definition of a derivation of a string for a given ordered context-free grammar, and present a parsing algorithm, using shared packed parse forests, with time complexity O(n(4)), where n is the length of the input string being parsed.

引用

页码：140 / 153

页数：14