Wyniki wyszukiwania - BazTech

Ograniczanie wyników

4 Fundamenta Informaticae

4 Redziejowski R.R.

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: parsing expression grammar

Sortuj według:

Ogranicz wyniki do:

BITES Instead of FIRST for Parsing Expression Grammar

Redziejowski R.R.

Fundamenta Informaticae

2011

Vol. 109, nr 3

323-337

In an earlier paper, the author adapted to Parsing Expression Grammars (PEGs) the properties FIRST and FOLLOW used in the construction of predictive top-down parsers. The purpose was to obtain warnings for possible ”language hiding”. It turned out that FIRST does not work well with lookahead expressions. To repair this, it is replaced here by a property named BITES that is a set of input strings instead of terminals.

Applying Classical Concepts to Parsing Expression Grammar

Redziejowski R.R.

Fundamenta Informaticae

2009

Vol. 93, nr 1-3

325-336

The paper is an attempt to see how much we can learn about a given Parsing Expression Grammar with the help of classical concepts used in the construction of predictive top-down parsers.

Some Aspects of Parsing Expression Grammar

Redziejowski R.R.

Fundamenta Informaticae

2008

Vol. 85, nr 1-4

441-454

Parsing Expression Grammar (PEG) is a new way to specify syntax, by means of a top-down process with limited backtracking. It can be directly transcribed into a recursive-descent parser. The parser does not require a separate lexer, and backtracking removes the usual LL(1) constraint. This is convenient for many applications, but there are two problems: PEG is not well understood as a language specification tool, and backtracking may result in exponential processing time. The paper consists of two parts that address these problems. The first part is an attempt to find out the language actually defined by a given parsing expression. The second part reports measurements of backtracking activity in a PEG-derived parser for the programming language C.

Parsing Expression Grammar as a Primitive Recursive-Descent Parser with Backtracking

Redziejowski R.R.

Fundamenta Informaticae

2007

Vol. 79, nr 3-4

513-524

Two recent developments in the field of formal languages are Parsing Expression Grammar (PEG) and packrat parsing. The PEG formalism is similar to BNF, but defines syntax in terms of recognizing strings, rather than constructing them. It is, in fact, precise specification of a backtracking recursive-descent parser. Packrat parsing is a general method to handle backtracking in recursive-descent parsers. It ensures linear working time, at a huge memory cost. This paper reports an experiment that consisted of defining the syntax of Java 1.5 in PEG formalism, and literally transcribing the PEG definitions into parsing procedures (accidentally, also in Java). The resulting primitive parser shows an acceptable behavior, indicating that packrat parsing might be an overkill for practical languages. The exercise with defining the Java syntax suggests that more work is needed on PEG as a language specification tool.