context-free grammar


Also found in: Acronyms, Wikipedia.

context-free grammar

[′kän‚tekst ‚frē ′gram·ər]
(computer science)
A grammar in which any occurrence of a metavariable may be replaced by one of its alternatives.
References in periodicals archive ?
For instance, students recognize that Backus-Naur diagrams, commonly used to define the syntax of PASCAL statements, are equivalent to context-free grammars (type 2 in Chomsky hierarchy).
Let G' be a context-free grammar constructed from a regular tree grammar in normal form.
Basic Methods of Probabilistic Context-Free Grammars.
Proof: This comes as a nice consequence of our Theorem 3: all the families of planar maps of [BFSS01] cannot be generated by an unambiguous context-free grammar, because of their critical exponent 3/2.
Roughly, a parser for a context-free grammar is a function that maps a sequence of terminals [Xi] to a derivation from the start symbol to [Xi].
First and foremost, they are the obvious extension in the statistical domain of the ubiquitous context-free grammars that most computer scientists and linguists are already familiar with.
The act of mentioning a nonliteral terminal symbol, such as xIdentifier, in the context-free grammar and in the .
Although you can't deal with a language that has redoubling and duplication using a context-free grammar, and therefore there are certain parsing techniques, familiar in computer scient, that won't work on a language like that," he says, "nevertheless, you can easily devise another technique that will.
Consider the graph and the context-free grammar shown in Figure 1.
A context-free grammar G generating a binary tree is given below, where root, inter, and leaf are terminals (basic processes), and S and SUB are nonterminals.
By design, our prototype architectures are sufficiently general to support translations into and from any standard form expressible as a context-free grammar.

Full browser ?