Class Notes (1,100,000)
US (480,000)
KSU (2,000)
CS (9)
Lecture 3

CS 33101 Lecture Notes - Lecture 3: Parsing, Lexeme, Formal Language

Computer Science
Course Code
CS 33101
Younghun Chae

This preview shows page 1. to view the full 4 pages of the document.
CS33101 Day 3 September 3
Describing Syntax and Semantics
Formal Language Specification
• Programming languages are only useful if they are “understood” by a computer
• In order to insure this, programming language must have:
A concise form (syntax)
A concise meaning (semantics)
Neither one can be ambiguous
Syntax: the part of the language definition that says what program look like
Their form and structure of the expressions, statements, and program units
Semantics: the part of the language definition that says what programs do
their behavior and meaning of the expressions, statements, and program units
• Syntax and semantics provide a language’s definition
Users of a language definition
• Other language designers
• Implementers
• Programmers (the users of the language)
• In order to insure conciseness of language specifications we need tools
Grammars are used to define the syntax
Mathematical constructs (such as functions and sets) are used to define the
The General Problem of Describing Syntax: Terminology
• A sentence is a string of characters over some alphabet
• A language is a set of sentences
• A lexeme is the lowest level syntactic unit of a language (e.g., *, sum, begin)
• A token is a category of lexemes (e.g., identifier)
Formal Definition of Languages
A recognition device reads input strings over the alphabet of the language and
decides whether the input strings belong to the language
Example: syntax analysis part of a compiler
- Detailed discussion of syntax analysis appears in Chapter 4
A device that generates sentences of a language
One can determine if the syntax of a particular sentence is syntactically correct
by comparing it to the structure of the generator
You're Reading a Preview

Unlock to view full version