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 条
  • [11] On restricted context-free grammars
    Dassow, Juergen
    Masopust, Tomas
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2012, 78 (01) : 293 - 304
  • [12] RELATEDNESS OF CONTEXT-FREE GRAMMARS
    WALTER, HKG
    COMPUTING, 1979, 22 (01) : 31 - 58
  • [13] On Restricted Context-Free Grammars
    Dassow, Juergen
    Masopust, Tomas
    DEVELOPMENTS IN LANGUAGE THEORY, 2010, 6224 : 434 - +
  • [14] PREDICTORS OF CONTEXT-FREE GRAMMARS
    TAI, KC
    SIAM JOURNAL ON COMPUTING, 1980, 9 (03) : 653 - 664
  • [15] CONTEXT-FREE GRAPH GRAMMARS
    DELLAVIGNA, P
    GHEZZI, C
    INFORMATION AND CONTROL, 1978, 37 (02): : 207 - 233
  • [16] On Muller Context-Free Grammars
    Esik, Zoltan
    Ivan, Szabolcs
    DEVELOPMENTS IN LANGUAGE THEORY, 2010, 6224 : 173 - 184
  • [17] On Muller context-free grammars
    Esik, Zoltan
    Ivan, Szabolcs
    THEORETICAL COMPUTER SCIENCE, 2012, 416 : 17 - 32
  • [18] On a construction of context-free grammars
    Martinek, Pavel
    Fundamenta Informaticae, 2000, 44 (03) : 245 - 264
  • [19] ON CONTEXT-FREE PROGRAMMED GRAMMARS
    SEBESTA, RW
    COMPUTER LANGUAGES, 1989, 14 (02): : 99 - 108
  • [20] MINIMIZATION OF CONTEXT-FREE GRAMMARS
    Ryazanov, Yu D.
    Nazina, S., V
    PRIKLADNAYA DISKRETNAYA MATEMATIKA, 2019, (45): : 90 - 96
12345