Context-free grammar, syntax and nested structure

By UK A Level Computer Science · independent study · myAudience

Original textbook concept plate generated with OpenAI imagegen; labels and states checked against the lesson model. · Generated original teaching artwork; pending operator rights/provenance review before publication.

Context-free grammar, syntax and nested structure

A grammar specifies how permitted strings can be formed. In Backus–Naur Form, nonterminals name syntactic categories, terminals are literal symbols and productions give alternatives for expanding a nonterminal. Our original balanced-parenthesis language uses S::= "(" S ")" S | ε. The start symbol is S, the terminals are ( and ), and ε denotes an empty expansion. A derivation repeatedly applies productions until only terminals remain. Syntax concerns formation; it does not automatically describe meaning, data types or suitability for a real task.

The first S inside the parentheses represents a nested balanced group; the second S represents any following balanced groups. Both are needed: omitting the second S allows nesting but not concatenations such as ()(). The ε production makes the empty string valid and supplies a stopping case for derivations. Recursion in a grammar is not a promise that a specific parser terminates: left-recursive rules can cause naive recursive-descent code to recurse without consuming input. Grammar expressiveness and parser implementation are separate questions.

For (()), first expand the outer S as (S)S, expand the inner S as (S)S, then expand all remaining S symbols as ε. Reading the terminal yield gives (()). A syntax tree records the hierarchical nesting, while the linear word records only the order of characters. A syntax diagram provides another way to show permitted paths through choices and repetitions. Checking a word against a grammar means demonstrating a valid derivation or explaining why none can exist, not merely noting that it has some familiar symbols.

The supplied recogniser counts current nesting depth. Each opening parenthesis increases depth and each closing one decreases it. A negative depth means a closing parenthesis lacks an earlier unmatched opener, so reject immediately. Accept only if depth is zero at the end. Equal total counts alone are insufficient: )( has one of each but violates the prefix condition. The invariant says depth equals openings minus closings in the consumed prefix, and no accepted prefix has negative depth. This gives O(n) time; depth grows up to n, requiring O(log n) bits even though it uses one Python integer variable.

No fixed finite-state recogniser can recognise arbitrarily deep balanced nesting. With only k states, prefixes of zero through k opening parentheses include two different lengths that reach the same state. Appending enough closing parentheses to balance the shorter prefix would produce the same final state for both, accepting one balanced word and one unbalanced word alike. The contradiction shows why remembering an unbounded depth needs more than finite state. Context-free grammar can express this language. It does not follow that every context-free language has an equally simple counter recogniser, nor that every practical parsing problem is context-free.

Reading the diagram: The left word (()) has depth 1,2,1,0 after its four symbols and no negative prefix. The right word )( reaches −1 immediately and the supplied recogniser stops. Its dotted second point at 0 is hypothetical: equal final counts would not repair the failed prefix. The grammar permits nesting and concatenation because it has both an inner S and a trailing S, plus ε. The graphs show a count state; they are not a syntax tree or proof that a finite-state machine handles unlimited depth.

Runnable original Python 3, independently executed on Python the related topic. Read the stated input contract before running. These examples use fictional data and are teaching models, not production services.

```python
def balanced(word):
"""Recognise S::= '(' S ')' S | epsilon with a stack depth counter."""
depth = 0
for symbol in word:
if symbol == '(':
depth += 1
elif symbol == ')':
depth -= 1
else:
raise ValueError('parenthesis alphabet required')
if depth < 0:
return False
return depth == 0
```

Worked example: Give a derivation of ()() and compare recognition of (()), )( and (().

S⇒(S)S⇒()S by replacing the first inner S with ε.

Expand the trailing S as (S)S, then replace its two nonterminals with ε to obtain ()().

Depth traces for (()) are 1,2,1,0; )( starts at −1 and fails; (() ends at 1 and fails.

Answer: ()() and (()) are valid; )( and (() are invalid for different reasons.

Check your understanding: 1. Is ε valid? 2. What language does S::= "(" S ")" | ε generate? 3. For a maximum permitted nesting depth of two, explain why a finite-state recogniser becomes possible and sketch its state meanings.

Answer: 1. Yes, through the ε alternative. 2. It generates one nested chain, (ⁿ)ⁿ for n≥0, excluding ()() because there is no trailing S. 3. Use depth states 0,1,2 and a rejecting sink. An opener increments unless already at 2; a closer decrements unless at 0; invalid moves go to the sink. Start and accept at 0. The explicit finite bound removes the need for unbounded memory.

Why: Equal numbers of opening and closing symbols do not guarantee valid order. ε is not an actual parenthesis token. The finite-state impossibility concerns unbounded nesting; a bounded engineering requirement is a different language. Syntax correctness does not establish semantic correctness.