Where does LL parser belong in the top

在请求帮助或建议时，用'in the event of...'而非'要是...就好了' #生活技巧# #职场沟通技巧# #商务英语#

First let's make some general remarks about nomenclature. They are not all relevant here, but they may help you in the future.

not all authors are using the same precise definition. Sometimes the differences are irrelevant for the current points, sometimes one wonder way such different things are named in the same way by different authors. Sometimes authors give the definition they are using, but that's not always true. Sometimes there are well accepted definition that you can take for granted in about any context, sometimes every group tend to have its own and you have to know of which group the author is a member. (Ask a Java and a ML programmer what polymorphism is)

Nomenclature are about classification. Classification is emphasizing some aspects while ignoring other, even if you think it should be (For instance L. Cardelli and P. Wegner do not consider the static or dynamic aspect in their analysis of polymorphism)

Now you are somewhat lucky, as some of the terms here have quasi-universal definitions (that is not that some are not using other one, especially in blogs and QA sites, but they are trying to intuit a definition from the terms instead of looking at the definitions given by text books).

A top-down parser is a parser which start from the start symbol, guess which production to use, and then repeat the process for a non terminal symbol. If it is able to second guess its choice, it is also a back-tracking parser. If it never second guess its choice, it is a deterministic parser.

A LL(k) parser is a deterministic top-down parser which will always determine the production to use for the left-most non-terminal not yet determined (that's what the second L means) and will consider only the text from left to right (that's what the first L means) and will never use more than $k$ terminal symbols not predicted.

Thus

There are four types of top-down parsers:

recursive descent backtracking recursive descent predictive table-driven with backtracking table-driven predictive.

deterministic seems more common than predictive but that division seems correct. I'll emphasize the fact that the division backtracking/predictive characterizes the algorithm, while the division recursive/table-driven characterizes the implementation. So although the classification is correct, it is mixing different aspects something which tend to introduce confusion.

All top down parsers are LL

That is false. Some are not deterministic (the recursive descent backtracking one of your first list). Some are scanning the text from right to left (AFAIK, the only interest is academic here but it would not surprise me that there is someone somewhere which found a use for it). Some are trying to determine the production to use for another non-terminal than the next one (it's a formalization of the good old find the next matching parenthesis before trying to parse what is between them).

LL is usually a more efficient parsing technique than recursive-descent.

LL can be implemented as recursive-descent (and is the easiest way to do so), opposing the two does not really make sense to me. Recursive/table driven is an implementation choice. (I've written both, I'd use the table driven approach only as part of a parser generator but I'll never say they are different algorithms).

LL parsers are also called predictive

This could be misleading. They are not the only class of parser which could be called predictive.

网址：Where does LL parser belong in the top https://klqsh.com/news/view/114138

相关内容

Where to Get the Best Pizza in Paris
“One of the Finest Hotels in Texas” since 1886
Top 10 Best Coffee Shops In Newport Beach, California
Where Is “Quick Access” In Windows 11 File Explorer?
The 10 Best Wedding Venues in Chicago
The 10 Best Wedding Venues in Birmingham
The 5 Best Espresso Martinis in Newport Beach
The Role of Sclerostin in Bone Diseases
The 10 Best Wedding Venues in Dallas
File Explorer in Windows

随便看看