A Left to Right then Right to Left Parsing Algorithm
Determination of the minimum resources required to parse a language generated by a given context free grammar is an intriguing and yet unsolved problem. It seems plausible that any unambiguous context free grammar could be parsed in time proportional to the length, n, of each input string. Early (2)...
| Main Author: | |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Online Access: | http://hdl.handle.net/1721.1/6160 |
| _version_ | 1826203766463922176 |
|---|---|
| author | Martin, William A. |
| author_facet | Martin, William A. |
| author_sort | Martin, William A. |
| collection | MIT |
| description | Determination of the minimum resources required to parse a language generated by a given context free grammar is an intriguing and yet unsolved problem. It seems plausible that any unambiguous context free grammar could be parsed in time proportional to the length, n, of each input string. Early (2) has presented an algorithm which parses "many" grammars in the proportional to n, but requires n2 on some. His work is an extension of Knuth's method. Knuth's method fails when more than one alternative must be examined by a push-down automation making a left to right scan of the input string. Early's extension takes all possible alternatives simultaneously without duplication of effort at any given one step. The method presented here continues through the string in order to gain pass, which is made on the symbols accumulated on the stack of the automation. The algorithm is probably more efficient than Early's on certain grammars; it will fail completely on others. The essential idea may be interesting to those attacking the general problem. |
| first_indexed | 2024-09-23T12:42:42Z |
| id | mit-1721.1/6160 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:42:42Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/61602019-04-12T07:44:02Z A Left to Right then Right to Left Parsing Algorithm Martin, William A. Determination of the minimum resources required to parse a language generated by a given context free grammar is an intriguing and yet unsolved problem. It seems plausible that any unambiguous context free grammar could be parsed in time proportional to the length, n, of each input string. Early (2) has presented an algorithm which parses "many" grammars in the proportional to n, but requires n2 on some. His work is an extension of Knuth's method. Knuth's method fails when more than one alternative must be examined by a push-down automation making a left to right scan of the input string. Early's extension takes all possible alternatives simultaneously without duplication of effort at any given one step. The method presented here continues through the string in order to gain pass, which is made on the symbols accumulated on the stack of the automation. The algorithm is probably more efficient than Early's on certain grammars; it will fail completely on others. The essential idea may be interesting to those attacking the general problem. 2004-10-04T14:43:39Z 2004-10-04T14:43:39Z 1968-02-01 AIM-155 http://hdl.handle.net/1721.1/6160 en_US AIM-155 6369225 bytes 515662 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Martin, William A. A Left to Right then Right to Left Parsing Algorithm |
| title | A Left to Right then Right to Left Parsing Algorithm |
| title_full | A Left to Right then Right to Left Parsing Algorithm |
| title_fullStr | A Left to Right then Right to Left Parsing Algorithm |
| title_full_unstemmed | A Left to Right then Right to Left Parsing Algorithm |
| title_short | A Left to Right then Right to Left Parsing Algorithm |
| title_sort | left to right then right to left parsing algorithm |
| url | http://hdl.handle.net/1721.1/6160 |
| work_keys_str_mv | AT martinwilliama alefttorightthenrighttoleftparsingalgorithm AT martinwilliama lefttorightthenrighttoleftparsingalgorithm |