History: General Parsing

Source of version: 1 (current)

There are algorithms which can parse any context-free language, ambiguous or not. Earley's Algorithm and Tomita's Parser are such parsers. * Earley's: A chart parsing algorithm with a complexity of O(n^3), though it is very close to O(n) for ((LR))(k) grammars, and remains roughly O(n^2) for grammars which are only mildly ambiguous. * Tomita's: A parser which is based on using an LR(0) parser that splits the parsing in multiple directions whenever ambiguity is encountered. If one of the forks has an error (meaning it wouldn't produce a valid parse), then it is terminated. It remains O(n) for languages which are LR(0), and the additional complexity increases about linearly with the number of ambiguities encountered. (Ambiguities as far as an LR(0) language is concerned.) General parsers get a bad rap (IMO, --jay), for being excessively complex and having bad computational complexities. With modern computers, though, and processing systems doing non-trivial semantic analysis of the language being parsed, you couldn't tell the difference between O(n^3) and O(n). ('Cause once you toss something like global register allocation into the mix, you're dealing with exponential times anyways...)

History

Enable pagination rows per page

HTML diff Side-by-side diff Side-by-side diff by characters Inline diff Inline diff by characters Full side-by-side diff Full side-by-side diff by characters Full inline diff Full inline diff by characters Unified diff Side-by-side view HTML diff Side-by-side diff Advanced

Information	Version
Fri 30 of Nov, 2001 12:31 GMT admin from admin created from phpwiki import	1

Select action to perform with checked... Remove OK