You are here
practical methodology for strong LL(k) parsing
| Title: | A practical methodology for strong LL(k) parsing. |
 158 views 67 downloads |
|---|---|---|
| Name(s): |
Feriozi, Dan T. Florida Atlantic University, Degree Grantor Levow, Roy B., Thesis advisor College of Engineering and Computer Science Department of Computer and Electrical Engineering and Computer Science |
|
| Type of Resource: | text | |
| Genre: | Electronic Thesis Or Dissertation | |
| Issuance: | monographic | |
| Date Issued: | 1996 | |
| Publisher: | Florida Atlantic University | |
| Place of Publication: | Boca Raton, Fla. | |
| Physical Form: | application/pdf | |
| Extent: | 243 p. | |
| Language(s): | English | |
| Summary: | A new method of analyzing and parsing the strong LL(k) class of the deterministic context-free grammars is presented. The method is shown to be efficient when applied to many typical parsing applications such as compilers for common programming languages. Another advantage of the method is that it uses the familiar LL(1) parse table as a base. Parse conflicts that are found in the LL(1) parse table are treated as exceptions, and are resolved by consulting another table. This extension to the traditional LL(1) methodology increases its power significantly. Both the space and the time efficiency of the new method are shown to be much greater than that of the standard strong LL(k) method, when used on common grammars. Since the recognition problem for the strong LL(k) grammars is known to be NP-complete, the worst-case complexity of the new method is exponential, as is the case with the standard method. However, the complexity of the new method is highly dependent on the form of the grammar that is being analyzed. Both the space requirements and the time complexity of the new method are polynomial functions of the size of the input to the problem for common grammars, such as those used for programming languages. This is in contrast to the standard method that has been used for parsing the strong LL(k) languages. That method always uses space and time that is an exponential function of the size of the input. | |
| Identifier: | 9780591159974 (isbn), 12488 (digitool), FADT12488 (IID), fau:9380 (fedora) | |
| Collection: | FAU Electronic Theses and Dissertations Collection | |
| Note(s): |
College of Engineering and Computer Science Thesis (Ph.D.)--Florida Atlantic University, 1996. |
|
| Subject(s): |
Parsing (Computer grammar) Formal languages |
|
| Held by: | Florida Atlantic University Libraries | |
| Persistent Link to This Record: | http://purl.flvc.org/fcla/dt/12488 | |
| Sublocation: | Degree grantor | |
| Use and Reproduction: | Copyright © is held by the author, with permission granted to Florida Atlantic University to digitize, archive and distribute this item for non-profit research and educational purposes. Any reuse of this item in excess of fair use or other copyright exemptions requires permission of the copyright holder. | |
| Use and Reproduction: | http://rightsstatements.org/vocab/InC/1.0/ | |
| Host Institution: | FAU | |
| Is Part of Series: | Florida Atlantic University Digital Library Collections. |
