Formalization and correctness of predictive shift-reduce parsers for graph grammars based on hyperedge replacement

被引：14

作者：

Drewes, Frank ^{[1
]}

Hoffmann, Berthold ^{[2
]}

Minas, Mark ^{[3
]}

机构：

[1] Umea Univ, Inst Datavetenskap, SE-90187 Umea, Sweden

[2] Univ Bremen, Fachbereich Informat 3, D-28334 Bremen, Germany

[3] Univ Bundeswehr Munchen, Inst Softwaretechnol, Fak Informat, D-85577 Neubiberg, Germany

来源：

JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN PROGRAMMING | 2019年 / 104卷

关键词：

Hyperedge replacement grammar; Graph parsing; Grammar analysis; LANGUAGES;

D O I：

10.1016/j.jlamp.2018.12.006

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Hyperedge replacement (HR) grammars can generate NP-complete graph languages, which makes parsing hard even for fixed HR languages. Therefore, we study predictive shift-reduce (PSR) parsing that yields efficient parsers for a subclass of HR grammars, by generalizing the concepts of SLR(1) string parsing to graphs. We formalize the construction of PSR parsers and show that it is correct. PSR parsers run in linear space and time, and are more efficient than the predictive top-down (PTD) parsers recently developed by the authors. (C) 2019 Elsevier Inc. All rights reserved.

引用

页码：303 / 341

页数：39