Context-Free Grammar (CFG)

In a context-free grammar (CFG), terminals are symbols that can be further replaced by other terminals or non-terminals.

The 'start symbol' in a context-free grammar (CFG) is a terminal symbol, typically denoted by 'S', from which derivations begin.

Parsing a sentence involves determining the semantic meaning of a sentence based on the rules of grammar.

A derivation, in the context of formal grammars, illustrates the sequence of applying grammatical rules to transform the start symbol into a string of non-terminals.

Productions in a context-free grammar dictate how terminal symbols can be transformed into non-terminal symbols.

Syntax encompasses the rules governing the meanings of words and their relationships within a language.

Given a CFG with the production rules S → aS | b, the language generated by the CFG include words with any number of 'a's followed by a single 'b'.

If a context-free grammar has two or more distinct derivation trees for the same sentence, the grammar is considered unambiguous.

In a context-free grammar (CFG) designed for mathematical expressions, productions for operators with higher precedence, such as * and /, should appear before productions for operators with lower precedence, such as + and -.

The start symbol in a context-free grammar (CFG) is placed at the root of the syntax tree when graphically representing the derivation of a word.

The leaves of a syntax tree in a context-free grammar (CFG) will be non-terminals, representing intermediate steps in the derivation.

A context-free grammar (CFG) is considered unambiguous if there exists at least one word that can be generated by two distinct syntax trees.

In constructing a syntax tree for the expression $5 + 3 * 2$, the production rule for + should appear at a lower level in the tree than the production rule for *.

If a context-free grammar (CFG) has two different leftmost derivations for the same word, it is guaranteed to also have two different rightmost derivations for that word.

In a context-free grammar (CFG), if a non-terminal appears on the left side of a production rule, it must appear at the extreme right of each of its productions.

When drawing a syntax tree, the operator that is evaluated first should have its production appear at the topmost level of the tree.

If a context-free grammar (CFG) can generate the word 'abab' and 'abba', then it proves the CFG is unambiguous.

A context-free grammar (CFG) with the production rule S -> aS | Sa | a generates the language a*, including the empty string.

The Context-Free Grammar (CFG) S -> aS | ^ generates the language of all strings of 'a's, including the empty string.

A CFG with the productions S -> SS, S -> a, and S -> ^ can generate any number of 'a's, including the null string, but each word can only be generated in one way.

The CFG defined by S -> aS | bS | a | b generates the language (a+b)*, representing all possible strings of 'a's and 'b's, including the empty string.

Adding the production S -> ^ to the CFG S -> aS | bS | a | b will result in a grammar that generates the language (a+b)*.

If a CFG has multiple ways to generate a particular word, it is considered ambiguous.

A CFG defined as S -> X | Y, X -> aX | bX | a | b, and Y -> ^ generates the language (a+b)*, where every word has multiple derivations.

A Context-Free Grammar (CFG) for even palindromes can be represented as S -> aSa | bSb | ^.

The language consisting of strings with an equal number of a's and b's is regular.

The Context-Free Grammar S -> aSa | bSb | a | b | ^ will generate all possible palindrome.

Given the CFG S -> aB | bA, A -> a | aS | bAA, and B -> b | bS | aBB, it is possible to derive the string 'aabb' starting from S.

If you have the productions X -> aX | bX | ^, then X can generate any string of a's and b's including null.

The CFG productions S -> XY, X -> aX | bX | a, and Y -> Ya | Yb | a can only generate strings that start and end with a.

The following CFG S -> aSb | ^ generates strings with an equal number of as and bs with the as appearing before the bs.

In a CFG for arithmetic expressions, the rule Expr -> Expr + Term | Expr - Term | Term implies that addition and subtraction are right-associative.

A CFG that directly encodes operator precedence (e.g., using separate rules for terms and factors) will be ambiguous.

Context Free Grammar (CFG)

Terminals

Non-Terminals

Productions

Derivation

Parsing a Sentence

Syntax

Ambiguous Grammar

Non-terminal in CFG

Operator precedence

Syntax tree

Leaves in a syntax tree

Left-most derivation

Right-most derivation

Production rule

Derivation in CFG

Expression evaluation order

Language a*

CFG

Language (a+b)+

Language (a+b)*

Odd Palindrome

Even Palindrome

Language EQUAL

Identifier in C

Expression Grammar

Left recursive grammar

Right associative operators