Back التحليل من أعلى إلى أسفل Arabic Syntaktická analýza shora dolů Czech تحلیلگر بالا به پایین Persian Parsiranje od vrha prema dnu Croatian トップダウン構文解析 Japanese 하향식 구문 분석 Korean Ovenfra-ned-parser NB Analiza zstępująca Polish Análise de cima para baixo Portuguese Parsare top-down Romanian

Top-down parsing

Top-down parsing in computer science is a parsing strategy where one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar.[1] LL parsers are a type of parser that uses a top-down parsing strategy.

Top-down parsing is a strategy of analyzing unknown data relationships by hypothesizing general parse tree structures and then considering whether the known fundamental structures are compatible with the hypothesis. It occurs in the analysis of both natural languages and computer languages.

Top-down parsing can be viewed as an attempt to find left-most derivations of an input-stream by searching for parse-trees using a top-down expansion of the given formal grammar rules. Inclusive choice is used to accommodate ambiguity by expanding all alternative right-hand-sides of grammar rules.[2]

Simple implementations of top-down parsing do not terminate for left-recursive grammars, and top-down parsing with backtracking may have exponential time complexity with respect to the length of the input for ambiguous CFGs.[3] However, more sophisticated top-down parsers have been created by Frost, Hafiz, and Callaghan,[4][5] which do accommodate ambiguity and left recursion in polynomial time and which generate polynomial-sized representations of the potentially exponential number of parse trees.

  1. ^ Dick Grune; Ceriel J.H. Jacobs (29 October 2007). Parsing Techniques: A Practical Guide. Springer Science & Business Media. ISBN 978-0-387-68954-8.
  2. ^ Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986). Compilers, principles, techniques, and tools (Rep. with corrections. ed.). Addison-Wesley Pub. Co. ISBN 978-0201100884.
  3. ^ Aho, Alfred V.; Ullman, Jeffrey D. (1972). The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.) (Repr. ed.). Englewood Cliffs, NJ: Prentice-Hall. ISBN 978-0139145568.
  4. ^ Frost, R., Hafiz, R. and Callaghan, P. (2007) " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars ." 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109 - 120, June 2007, Prague. Archived from the original on 12 November 2018.
  5. ^ Frost, R., Hafiz, R. and Callaghan, P. (2008) " Parser Combinators for Ambiguous Left-Recursive Grammars." 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167-181, January 2008, San Francisco.

Developed by StudentB