Trees occur in various venues in computer science: decision trees in algorithms,

Question

Trees occur in various venues in computer science: decision trees in algorithms, search trees, and so on. In linguistics, one encounters trees as well, typically as parse trees, which are essentially sentence diagrams, such as those you might have had to do in primary school, breaking a natural-language sentence into its components%u2014clauses, subclauses, nouns, verbs, adverbs, adjectives, prepositions, and so on. What might be the significance of the depth and breadth of a parse tree relative to the sentence it represents? If you need to, look up parse tree and natural language processing on the Internet to see some examples.

Please explain

Explanation / Answer

Top down parsing
Start with the starting symbol S
Given current string x A y, and a rule A ? w, rewrite the string as x w y
Here A is a non-terminal symbol, x, y, and w may be terminal and/or non-terminal symbols,
may also be empty.
If we can derive the input string from S, then the input string belongs to the language.

Building the parse tree:

Initially we build a parse tree of one node - S.
Then, each time a rule A ? A1 A2 %u2026 An is used, we create nodes A1, A2, .. An
and link them as children to the node A.
Here A is a non-terminal symbol, A1, A2,%u2026An may me terminal and /or non-terminal symbols.

Bottom up parsing
Start with the input string
If the current string is x w y and there is a rule A ? w, rewrite the string as x A y
If we can derive S from the input string, then the input string belongs to the language.

Building the parse tree:

For an input string of length N initially we create N nodes, corresponding to the terminal symbols.
Then, each time a rule A ? A1 A2 %u2026 An is used, we create a node A and link it
as a parent node to the nodes A1, A2, %u2026.An.


Non-detereminism
This is the case when at a given step more than one rule can be applied
Non-detereminism is handled by exploring all possibilities


Breadth-first and Depth-first search
Given a tree, we can visit its nodes in a depth-first manner (working down a path )
or in a breadth-first manner (working level by level)

In the parsing process we build a parse tree. If more than one rule can be applied, the process itself can be represented as a tree, each node corresponding to a currently built parse tree.

Hence, depth-first or breadth-first search refer to the way we accomplish the parsing process.


Complexity of parsing
The top-down and bottom-up parsing methods described above fall into the category of exhaustive search algorithms. At each derivation step we apply a grammar rule either increasing the length of the current string from 1 symbol (the starting symbol) to the target string (only terminal symbols) or decreasing the length from all terminal symbols to the starting symbol. Thus the number of the derivation steps is bound by the length of the parsed string.

At each step we may have a choice among several rules that expand the same non-terminal symbol (in top-down parsing), or that have the same right-hand side (in bottom-up parsing).

Therefore the complexity of the exhaustive parsing is exponential in the length of the parsed string and hence extremely inefficient.

There are two widely used algorithms for parsing, both based on dynamic programming, that reduce the complexity to O(n3), where n is the length of the parsed string: Earley%u2019s algorithm, published in 1970, and Cocke-Younger-Kasami (CYK) algorithm, developed 1965 %u2013 1967.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.