How does a computer read the grammar of code?
Before a computer runs your code, it diagrams it like a sentence, and the rules for that came from a linguist.
▶ Start the storyA computer reads code the way you once learned to read sentences in grammar class: it breaks the text into pieces, checks that the pieces fit together by the rules, and only then works out what they mean. That is parsing, the process of analyzing a string of symbols according to the rules of a by breaking it into parts. The word comes from the Latin for a part of speech, and parsing was once central to teaching grammar throughout the English-speaking world. A parser is the software component that takes the text and builds a hierarchical structure, such as a or an , while checking for correct syntax.
Parsing happens in stages. First, splits the stream of characters into meaningful symbols called : a calculator looking at 12 * (3 + 4)^2 splits it into 12, *, (, 3, +, 4, ), ^ and 2. Next, parsing proper checks that the tokens form an allowable expression, usually against a that recursively defines the pieces of an expression and the order they must appear in. The final phase works out the implications of the validated expression and takes the appropriate action: an interpreter evaluates it, while a compiler generates code.
Step 1:
Split the characters into : 12, *, (, 3, +, 4, ), ^, 2
Step 2: Parsing
Check the against a grammar and build a tree
Step 3: Semantic analysis
Work out what it means: an interpreter calculates, a compiler writes code
The grammar rules come from linguistics. Context-free grammars were invented by the linguist Noam Chomsky to describe the structure of sentences in natural language. The ALGOL project, from 1957 to 1960, used one to describe its syntax, and the notation for such descriptions became known as Backus-Naur form.
Why not just let computers parse English? Because human sentences are not easily parsed by programs: there is substantial ambiguity in the structure of human language. In "The boy saw the lady with the telescope", who has the telescope? Languages are often ambiguous by nature, so programming languages are often specified with a precisely to avoid that, and fast and efficient parsers can be written for them.
Quiz me
0/3
Recap
A parser splits text into tokens, checks them against a grammar and builds a tree, and only then does meaning get worked out.
💡 A trick to remember it · Split it, check it, tree it: tokens, grammar, then a tree.
Surprising fact · Context-free grammars were invented by the linguist Noam Chomsky for human sentences, then adopted for ALGOL.
Sources (3)
No source, no claim. Every fact in this lesson (16 claims) cites at least one of these.