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
相关论文
共 50 条
  • [1] Ordered Context-Free Grammars
    van der Merwe, Brink
    Berglund, Martin
    IMPLEMENTATION AND APPLICATION OF AUTOMATA (CIAA 2022), 2022, 13266 : 53 - 66
  • [2] ORDERED CONTEXT-FREE GRAMMARS
    LEPISTO, T
    INFORMATION AND CONTROL, 1973, 22 (01): : 56 - 68
  • [3] Context-free valence grammars - Revisited
    Hoogeboom, HJ
    DEVELOPMENTS IN LANGUAGE THEORY, 2002, 2295 : 293 - 303
  • [4] Generalized context-free grammars and multiple context-free grammars
    Kasami, Tadao
    Seki, Hiroyuki
    Fujii, Mamoru
    Systems and Computers in Japan, 1989, 20 (07): : 43 - 52
  • [5] Context-Free Tree Grammars are as Powerful as Context-Free Jungle Grammars
    Drewes, Frank
    Engelfriett, Joost
    ACTA CYBERNETICA, 2015, 22 (02): : 373 - 392
  • [6] CONTEXT-FREE GRAMMARS WITH MEMORY
    MORIYA, E
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 1992, E75D (06) : 847 - 851
  • [7] REDUCTION OF CONTEXT-FREE GRAMMARS
    TANIGUCHI, K
    KASAMI, T
    ELECTRONICS & COMMUNICATIONS IN JAPAN, 1969, 52 (12): : 204 - +
  • [8] On translating context-free grammars into Lambek grammars
    S. L. Kuznetsov
    Proceedings of the Steklov Institute of Mathematics, 2015, 290 : 63 - 69
  • [9] Context-Free Categorical Grammars
    Bauderon, Michel
    Chen, Rui
    Ly, Olivier
    ALGEBRAIC INFORMATICS, 2009, 5725 : 160 - +
  • [10] REDUCTION OF CONTEXT-FREE GRAMMARS
    TANIGUCHI, K
    KASAMI, T
    INFORMATION AND CONTROL, 1970, 17 (01): : 92 - +
12345