Inferring Context-Free Grammars for Domain-Specific Languages

被引：3

作者：

Crepinsek, Matej ^{[1
]}

Mernik, Marjan ^{[1
]}

Bryant, Barrett R. ^{[2
]}

Javed, Faizan ^{[2
]}

Sprague, Alan ^{[2
]}

机构：

[1] Univ Maribor, Fac Elect Engn & Comp Sci, SL-2000 Maribor, Slovenia

[2] Univ Alabama Birmingham, Dept Comp & Informat Sci, Birmingham, AL 35294 USA

来源：

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE | 2005年 / 141卷 / 04期

关键词：

Grammar induction; Grammar inference; Learning from positive and negative examples; Genetic programming; Exhaustive search;

D O I：

10.1016/j.entcs.2005.02.055

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In the area of programming languages, context-free grammars (CFGs) are of special importance since almost all programming languages employ CFG's in their design. Recent approaches to CFG induction are not able to infer context-free grammars for general-purpose programming languages. In this paper it is shown that syntax of a small domain-specific language can be inferred from positive and negative programs provided by domain experts. In our work we are using the genetic programming approach in grammatical inference. Grammar-specific heuristic operators and nonrandom construction of the initial population are proposed to achieve this task. Suitability of the approach is shown by examples where underlying context-free grammars are successfully inferred.

引用

页码：99 / 116

页数：18

共 50 条

[1] METHOD FOR INFERRING CONTEXT-FREE GRAMMARS
KNOBE, B
KNOBE, K
INFORMATION AND CONTROL, 1976, 31 (02): : 129 - 146
[2] Context-free grammars and XML languages
Bertoni, Alberto
Choffrut, Christian
Palano, Beatrice
DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS, 2006, 4036 : 108 - 119
[3] The Context-Free Grammars of Artificial Languages
Gribova, V. V.
Kleschev, A. S.
Krylov, D. A.
AUTOMATIC DOCUMENTATION AND MATHEMATICAL LINGUISTICS, 2013, 47 (02) : 59 - 67
[4] The context-free grammars of artificial languages
V. V. Gribova
A. S. Kleschev
D. A. Krylov
Automatic Documentation and Mathematical Linguistics, 2013, 47 (2) : 59 - 67
[5] COMPLEXITY AND UNAMBIGUITY OF CONTEXT-FREE GRAMMARS AND LANGUAGES
GRUSKA, J
INFORMATION AND CONTROL, 1971, 18 (05): : 502 - &
[6] ON PERMUTATIVE GRAMMARS GENERATING CONTEXT-FREE LANGUAGES
MAKINEN, E
BIT, 1985, 25 (04): : 604 - 610
[7] ON SOME TRANSFORMATIONS IN CONTEXT-FREE GRAMMARS AND LANGUAGES
CULIK, K
CZECHOSLOVAK MATHEMATICAL JOURNAL, 1967, 17 (02) : 278 - +
[8] Stepwise refining method for inferring context-free grammars
Zhang, Ruiling
Dong, Yunmei
Jisuanji Yanjiu yu Fazhan/Computer Research and Development, 2000, 37 (01): : 30 - 36
[9] Fuzzy context-free languages - Part 1: Generalized fuzzy context-free grammars
Asveld, PRJ
THEORETICAL COMPUTER SCIENCE, 2005, 347 (1-2) : 167 - 190
[10] NON-CONTEXT-FREE GRAMMARS GENERATING CONTEXT-FREE LANGUAGES
BAKER, BS
INFORMATION AND CONTROL, 1974, 24 (03): : 231 - 246

← 1 2 3 4 5 →