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
相关论文
共 34 条
[1]   ON THE MEMBERSHIP PROBLEM FOR REGULAR DNLC GRAMMARS [J].
AALBERSBERG, IJ ;
ROZENBERG, G ;
EHRENFEUCHT, A .
DISCRETE APPLIED MATHEMATICS, 1986, 13 (01) :79-85
[2]  
Aho Alfred V., 1972, The theory of parsing, translation, and compiling. 1: Parsing., V1
[3]  
[Anonymous], 2013, P 51 ANN M ASS COMP
[4]  
Banarescu L., 2013, LAW ACL
[5]   A parsing methodology for the implementation of visual systems [J].
Costagliola, G ;
De Lucia, A ;
Orefice, S ;
Tortora, G .
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1997, 23 (12) :777-799
[6]   THE MONADIC 2ND-ORDER LOGIC OF GRAPHS-V - ON CLOSING THE GAP BETWEEN DEFINABILITY AND RECOGNIZABILITY [J].
COURCELLE, B .
THEORETICAL COMPUTER SCIENCE, 1991, 80 (02) :153-202
[7]   CONTEXT-FREE GRAPH GRAMMARS [J].
DELLAVIGNA, P ;
GHEZZI, C .
INFORMATION AND CONTROL, 1978, 37 (02) :207-233
[8]   SIMPLE LR(K) GRAMMARS [J].
DEREMER, FL .
COMMUNICATIONS OF THE ACM, 1971, 14 (07) :453-&
[9]  
Drewes Frank, 2012, Applications of Graph Transformations with Industrial Relevance. 4th International Symposium, AGTIVE 2011. Revised Selected and Invited Papers, P182, DOI 10.1007/978-3-642-34176-2_16
[10]   RECOGNIZING K-CONNECTED HYPERGRAPHS IN CUBIC TIME [J].
DREWES, F .
THEORETICAL COMPUTER SCIENCE, 1993, 109 (1-2) :83-122
1234