Trying to Understand PEG.
Saved in:
| Title: | Trying to Understand PEG. |
|---|---|
| Authors: | Redziejowski, Roman R.1 roman@redz.se |
| Source: | Fundamenta Informaticae. 2018, Vol. 157 Issue 4, p463-475. 13p. |
| Subjects: | Parsing (Computer grammar), Backtrack programming, Syntax (Grammar), Algorithms, Scanning systems |
| Abstract: | Parsing Expression Grammar (PEG) encodes a recursive-descent parser with limited backtracking. Its properties are useful in many applications, but it is not well understood as a language definition tool. In its appearance, PEG is almost identical to a grammar in the Extended Backus-Naur Form (EBNF), and one may expect it to define the same language. But, due to the limited backtracking, PEG may reject some strings defined by EBNF, which gives an impression of PEG being unpredictable. We note that for some grammars, the limited backtracking is ”efficient”, in the sense that it exhausts all possibilities. A PEG with efficient backtracking should therefore be easy to understand. There is no general algorithm to check if the grammar has efficient backtracking, but it can be often checked by inspection. The paper outlines an interactive tool to facilitate such inspection. [ABSTRACT FROM AUTHOR] |
| Copyright of Fundamenta Informaticae is the property of Polskie Towarzystwo Matematyczne and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 127780322 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Trying to Understand PEG. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Redziejowski%2C+Roman+R%2E%22">Redziejowski, Roman R.</searchLink><relatesTo>1</relatesTo><i> roman@redz.se</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Fundamenta+Informaticae%22">Fundamenta Informaticae</searchLink>. 2018, Vol. 157 Issue 4, p463-475. 13p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Parsing+%28Computer+grammar%29%22">Parsing (Computer grammar)</searchLink><br /><searchLink fieldCode="DE" term="%22Backtrack+programming%22">Backtrack programming</searchLink><br /><searchLink fieldCode="DE" term="%22Syntax+%28Grammar%29%22">Syntax (Grammar)</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Scanning+systems%22">Scanning systems</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Parsing Expression Grammar (PEG) encodes a recursive-descent parser with limited backtracking. Its properties are useful in many applications, but it is not well understood as a language definition tool. In its appearance, PEG is almost identical to a grammar in the Extended Backus-Naur Form (EBNF), and one may expect it to define the same language. But, due to the limited backtracking, PEG may reject some strings defined by EBNF, which gives an impression of PEG being unpredictable. We note that for some grammars, the limited backtracking is ”efficient”, in the sense that it exhausts all possibilities. A PEG with efficient backtracking should therefore be easy to understand. There is no general algorithm to check if the grammar has efficient backtracking, but it can be often checked by inspection. The paper outlines an interactive tool to facilitate such inspection. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Fundamenta Informaticae is the property of Polskie Towarzystwo Matematyczne and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=127780322 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.3233/FI-2018-1638 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 13 StartPage: 463 Subjects: – SubjectFull: Parsing (Computer grammar) Type: general – SubjectFull: Backtrack programming Type: general – SubjectFull: Syntax (Grammar) Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Scanning systems Type: general Titles: – TitleFull: Trying to Understand PEG. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Redziejowski, Roman R. IsPartOfRelationships: – BibEntity: Dates: – D: 15 M: 02 Text: 2018 Type: published Y: 2018 Identifiers: – Type: issn-print Value: 01692968 Numbering: – Type: volume Value: 157 – Type: issue Value: 4 Titles: – TitleFull: Fundamenta Informaticae Type: main |
| ResultId | 1 |
