Derivációsfák

Derivációsfák, often translated as derivation trees or parse trees, are fundamental data structures in computer science and linguistics used to represent the syntactic structure of a string of symbols according to a formal grammar. They visually depict the process of deriving a string from a grammar's start symbol through a sequence of production rules. Each internal node in a derivation tree represents a non-terminal symbol from the grammar, and each leaf node represents a terminal symbol, which forms the actual string. The children of an internal node represent the symbols that replace the parent non-terminal according to a specific production rule.

The root of the tree is always the grammar's start symbol. Following a path from the root down to a leaf node, by concatenating the leaf symbols in order, reconstructs the original string. Derivation trees are crucial for understanding how a sentence or expression can be generated by a grammar and are widely used in compilers to parse source code, in natural language processing to analyze sentence structure, and in formal language theory to study the properties of languages defined by grammars. The construction and interpretation of derivation trees are directly tied to the specific context-free grammar used.