Context-free language . In Linguistics , Mathematics and Informatics and in the Chomsky hierarchy it refers to type 2 languages, those that can be represented by context-free grammars and finite automata .
They are the formal languages that encompass the regular languages and constitute the mechanisms of representation and recognition of programming languages from the syntactic point of view. Therefore, they have great application in the theory and construction of interpreters and compilers of programming languages (LP) or information specification or format , specifically in the parser or syntax parser that checks the syntax correctness in the LP source codes. .
Summary
[ hide ]
- 1 Definitions
- 2 Examples
- 3 Consequences
- 4 Importance
- 5 See also
- 6 Sources
Definitions
A language is said to be context-free (LLC) if and only if it can be recognized by a context-free grammar (GLC) G = <N, T, P, S> , where N is the set of nonterminal symbols or derivatives, T is the set of terminal symbols or alphabet ; P , the collection of productions of the form , where A is a nonterminal of N and ; S is the initial symbol.
A context free language (LLC) L is one whose strings can be recognized by stack automata.
Examples
One of the simplest cases of CLL is that of parentheses and that can be modeled with the LLC grammar .
This case of “matching” of parentheses (and other grouping signs) is very useful in arithmetic or other expressions within LPs, for example this case of a GLC that defines an assignment to a variable represented by its identifier of a typical Python arithmetic expression :
G = <{S, E, L}, {num, id, (,), +, -, *, /, //,%, =, **}, P, S>; where the production system P is defined: S => id = E E => id (L) E => (E) E => E ** E E => + E | -AND E => E * E | E / E | E // E | E% E | E => E + E | EE E => id | num L => E | THE
As can be seen, the call to functions and a kind of operational order of precedence have been included, which from the syntactic point of view does not have to be fulfilled but has been defined thus with the aim of illustrating the aspect of the precedence of arithmetic operations in LPs, a fact that is supported by automatic parser generators like Yacc.
Consequences
- An LLC can also be modeled as a set of all terminal sequences accepted by the equivalent GLC.
- The union and concatenation of two LLCs is also another LLC.
- The intersection of two LLCs is not necessarily an LLC.
- The inverse of an LLC is also LLC.
- An LLC plugin does not have to be context free.
- Regular languages are context free as they can be described using GLC.
- The productions of a regular grammarhave the form where
- The intersection of a context-free language and a regular language is always context-free.
- There are context-dependent grammars (GDCs) that are not context-free, although all GLCs are GDCs.
- To demonstrate that a given language is not context free, the Pumping Lemma can be used for context free languages.
- The problem of determining whether a context-sensitive grammar describes a context-free language is undecidable.
Importance
LLCs are of vital importance in the design and implementation of programming languages, since their computer implementations usually constitute the nuclei of parsers or parsers and are part of semantic analysis.
Subsets of LLCs such as LL (k) and LR (k) serve to automate the process of developing parents and there are consolidated tools such as Yacc, Bison , COCO / R , among others that favor the work of developers of LP; although it is often required that grammars have been reduced to these forms.
LLCs are also the basis of programs that serve to translate the source code of one LP into another or in software engineering modeling tools such as Rational Rose, which also transforms the diagrams of entities into sources of different LPs as desired by the developer.
