View in EDS

Generalized Bottom Up Parsers With Reduced Stack Activity.

Saved in:
Bibliographic Details
Title: Generalized Bottom Up Parsers With Reduced Stack Activity.
Authors: Scott, Elizabeth1 e.scott@rhul.ac.uk, Johnstone, Adrian1 a.johnstone@rhul.ac.uk
Source: Computer Journal. Sep2005, Vol. 48 Issue 5, p565-587. 23p.
Subjects: Parsing (Computer grammar), Linguistic String Parser (Computer grammar), Recursion theory, Algorithms, Asymptotic distribution
Abstract: We describe a generalized bottom up parser in which non-embedded recursive rules are handled directly by the underlying automaton, thus limiting stack activity to the activation of rules displaying embedded recursion. Our strategy is motivated by Aycock and Horspool's approach, but uses a different automaton construction and leads to parsers that are correct for all context-free grammars, including those with hidden left recursion. The automaton features edges which directly connnect states containing reduction actions with their associated goto state: hence we call the approach reduction incorporated generalized LR parsing. Our parser constructs shared packed parse forests in a style similar to that of Tomita parsers. We give formal proofs of the correctness of our algorithm, and compare it with Tomita's algorithm in terms of the space and time requirements of the running parsers and the size of the parsers' tables. Experimental results are given for standard grammars for ANSI-C, ISO-Pascal; for a non-deterministic grammar for IBM VS-COBOL, and for a small grammar that triggers asymptotic worst case behaviour in our parser. [ABSTRACT FROM PUBLISHER]
Copyright of Computer Journal is the property of Oxford University Press / USA 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 Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 44442417
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Generalized Bottom Up Parsers With Reduced Stack Activity.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Scott%2C+Elizabeth%22">Scott, Elizabeth</searchLink><relatesTo>1</relatesTo><i> e.scott@rhul.ac.uk</i><br /><searchLink fieldCode="AR" term="%22Johnstone%2C+Adrian%22">Johnstone, Adrian</searchLink><relatesTo>1</relatesTo><i> a.johnstone@rhul.ac.uk</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Computer+Journal%22">Computer Journal</searchLink>. Sep2005, Vol. 48 Issue 5, p565-587. 23p.
– 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="%22Linguistic+String+Parser+%28Computer+grammar%29%22">Linguistic String Parser (Computer grammar)</searchLink><br /><searchLink fieldCode="DE" term="%22Recursion+theory%22">Recursion theory</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Asymptotic+distribution%22">Asymptotic distribution</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We describe a generalized bottom up parser in which non-embedded recursive rules are handled directly by the underlying automaton, thus limiting stack activity to the activation of rules displaying embedded recursion. Our strategy is motivated by Aycock and Horspool's approach, but uses a different automaton construction and leads to parsers that are correct for all context-free grammars, including those with hidden left recursion. The automaton features edges which directly connnect states containing reduction actions with their associated goto state: hence we call the approach reduction incorporated generalized LR parsing. Our parser constructs shared packed parse forests in a style similar to that of Tomita parsers. We give formal proofs of the correctness of our algorithm, and compare it with Tomita's algorithm in terms of the space and time requirements of the running parsers and the size of the parsers' tables. Experimental results are given for standard grammars for ANSI-C, ISO-Pascal; for a non-deterministic grammar for IBM VS-COBOL, and for a small grammar that triggers asymptotic worst case behaviour in our parser. [ABSTRACT FROM PUBLISHER]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Computer Journal is the property of Oxford University Press / USA 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=44442417
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1093/comjnl/bxh102
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 23
        StartPage: 565
    Subjects:
      – SubjectFull: Parsing (Computer grammar)
        Type: general
      – SubjectFull: Linguistic String Parser (Computer grammar)
        Type: general
      – SubjectFull: Recursion theory
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Asymptotic distribution
        Type: general
    Titles:
      – TitleFull: Generalized Bottom Up Parsers With Reduced Stack Activity.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Scott, Elizabeth
      – PersonEntity:
          Name:
            NameFull: Johnstone, Adrian
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 09
              Text: Sep2005
              Type: published
              Y: 2005
          Identifiers:
            – Type: issn-print
              Value: 00104620
          Numbering:
            – Type: volume
              Value: 48
            – Type: issue
              Value: 5
          Titles:
            – TitleFull: Computer Journal
              Type: main
ResultId 1