Can a finite grammar describe infinitely many expressions?

Yes. Recursive productions can generate unbounded families of strings.

Does a grammar determine one structure for every accepted sentence?

Not necessarily. An ambiguous grammar permits more than one parse tree for some input.

Does passing a grammar check make an instruction meaningful?

No. Syntax and semantics are related but distinct layers of analysis.

AI Glossary / Graphs and symbolic AI / Intermediate

Grammar

Definition

A grammar is a formal description of how valid expressions can be structured in a language. In AI and computing, grammars are used to generate expressions, recognize allowed inputs, and analyze their internal organization. A context-free grammar, one common type, uses production rules that expand a category symbol into a sequence of symbols.

What it means

A grammar describes structural possibilities rather than merely listing every acceptable sentence. It can express that a command contains an action followed by an object, or that a sentence contains a noun phrase and a verb phrase. Repeated application of rules can describe many expressions compactly.
The term here concerns formal and computational grammar. It is not simply a checklist of preferred writing style. A grammar's coverage is also distinct from truth and meaning: an expression can fit a structural pattern while making a false, nonsensical, or inappropriate statement.

How it works

For a context-free grammar, specify terminal symbols, nonterminal categories, a start symbol, and production rules. Terminals are the final tokens of an expression. Nonterminals are categories that rules expand. Starting from the start symbol, apply productions until only terminals remain.
Parsing works in the other direction conceptually: given an input, determine whether the grammar can derive it and construct its structure. A string may have no parse, one parse, or several parses. Multiple structures for one string are grammatical ambiguity. Probabilistic or feature-based extensions can add information, but they do not eliminate the need to specify what the grammar represents.

Three practical examples

A controlled-language interface accepts a small set of commands with a defined action-object structure.
A natural-language processing lesson builds parse trees that show how words combine into larger phrases.
A programming-language tool checks whether a structured expression follows the syntax of a configuration or query language.

Think of it this way

Think of assembly instructions describing which kinds of components can fit together. The rules allow many finished structures without listing them individually. The analogy is limited because grammars can be recursive and ambiguous, and a structurally permitted expression need not correspond to a sensible physical assembly or meaningful instruction.

Worked example

Consider a fictional command grammar with start symbol Command. Its rules are Command → Action Object, Action → "open" or "close", and Object → "panel" or "drawer". The quoted words are terminals; Command, Action, and Object are nonterminals.
One derivation is Command → Action Object → open Object → open drawer. The grammar generates four two-word commands: open panel, open drawer, close panel, and close drawer. It cannot generate drawer open because the rule fixes the action before the object. It also cannot generate open blue drawer because no rule introduces blue.
Now add Object → Color Object and Color → "blue". The grammar admits open blue drawer, but recursion also permits open blue blue drawer and arbitrarily many repetitions. That may be structurally legal under the revised grammar while being undesirable for the intended interface. A rule that looks locally reasonable can therefore broaden the generated language more than expected.

Illustrative case study

In a fictional training application, the Linden team writes a small grammar for equipment commands. Test users enter polite forms and descriptive modifiers that the grammar does not cover. The team distinguishes two decisions: whether to expand the accepted language and whether each new construction has an unambiguous operational meaning.
It tests both valid and deliberately malformed inputs after revising the rules. The invented case shows that grammar design involves coverage and interpretation. It does not claim that a small command grammar can model unrestricted human language or safely execute every grammatical request.

Common misconceptions and mistakes

A grammar is not a parser: the grammar describes allowed structure, while a parser is an algorithm that analyzes input using that description. A parse tree is not automatically a complete semantic interpretation.
Do not assume that every grammatical sentence is true or useful. Do not confuse multiple derivation orders with genuinely different parse trees; ambiguity concerns alternative structures, not merely the order in which independent rule expansions were performed. Recursive rules require care because a finite grammar can describe infinitely many strings and some parsing strategies may loop on particular rule patterns.

Business use

Grammars can make structured interfaces more predictable by defining what forms an application accepts. They are also useful for validation, explanation, and transformation of formal expressions. The appropriate grammar depends on the desired language and the parser's capabilities.
For a business-facing interface, decide how unsupported input should be handled and how structure connects to meaning. A syntactically valid command may still refer to a nonexistent object or request an unavailable operation. Those checks belong to semantic and operational validation rather than being assumed from a successful parse.

Check your understanding

Why does adding Object → Color Object permit repeated blue modifiers in the worked example?

Answer: The right side contains Object again, so the same rule can be applied repeatedly before choosing the final panel or drawer rule. The recursion has no built-in limit on repetitions.

Related terms

Learn next

Learn next about parsing. Draw a tree for open blue drawer using the expanded grammar, then redesign the rules so an object can have at most one color modifier. Compare the accepted strings before and after the change, including a deliberately repeated modifier.

Parsing

Sources

Bird, Klein, and Loper, original NLTK book, Analyzing Sentence Structure: https://www.nltk.org/book/ch08.html NLTK official grammar module documentation: https://www.nltk.org/api/nltk.grammar.html

Previous: Gram matrix Next: Grammar-based code