Font size
Worksheets321 quiz 03 -- Grammars - BNF - syntax
Total questions: 24
Worksheet time: 13mins
<program> --> begin <stmt_list> end
A Java programming statement
A C++ programming statement
A javascript programming statement
is an example of a grammar rule , also called a production
A context-free grammar is a
formal grammar w/ production rules for all possible strings
formal grammar in which context is irrelevant
informal grammar
really not a grammar at all
John Backus is important to us because
he argued against the idea of context-free grammars
he introducing a formal language description notation, BNF
he describing ALGOL 58
he invented Fortran the first programming language
Noam Chomsky, a linguist, philosopher, social critic, and political activist,
Wrote the first compiler for Fortran
Wrote the first compiler for COBOL
Described 2 grammar classes known as context-free & regular
Worked @ MIT since 1955 and joined Univ of Arizona in 2018
A grammar is a
Set of rules for elementary or grammar school children
Formal language generation mechanism used to describe syntax
Often used in place of semantics
Only relevant to certain computer languages
Semantics is
The study of rhetoric
A form of argument
Includes the meaning of the expressions of software programs
An anti-virus company
formal language-genmeration mechanisms used to describe syntax of programming languages
Grammar
Context-Free Grammars
Backus-Naur Form
Metalanguage
used to describe the syntax of all programming languages, with minor exceptions
Grammar
Context-Free Grammars
Backus-Naur Form
Metalanguage
a natural notation for describing syntax - the most popular method of concisely describing programming language syntax today
Grammar
Context-Free Grammars
Backus-Naur Form
Metalanguage
a language that is used to describe another language. BNF = metalanguage for programming languages
Grammar
Context-Free Grammars
Backus-Naur Form
Metalanguage
each of the strings within a derivation
Sentential Form
Leftmost Derivations
Ambiguity
EBNF
a grammar that may generate more than one distinct parse trees for the same expression is ambiguous
Sentential Form
Leftmost Derivations
Ambiguity
EBNF
a specific order of symbol replacement in senential forms - the replaced nonterminal is always the left-most non-terminal in the previous sentential form
Sentential Form
Leftmost Derivations
Ambiguity
EBNF
extended BNF, designed to enhance readability for humans - no other benefit
Sentential Form
Leftmost Derivations
Ambiguity
EBNF
the abstraction being defined
In BNF: left-hand side
In BNF: right-hand side
In BNF: LHS and RHS
Nonterminal
Terminal
consists of some mixture of tokens, lexemes, and references to other abstractions
In BNF: left-hand side
In BNF: right-hand side
In BNF: LHS and RHS
Nonterminal
Terminal
a rule or production
In BNF: left-hand side
In BNF: right-hand side
In BNF: LHS and RHS
Nonterminal
Terminal
abstractions (left-hand side) of rules
In BNF: left-hand side
In BNF: right-hand side
In BNF: LHS and RHS
Nonterminal
Terminal
lexems and tokens (right-hand side) of rules
In BNF: left-hand side
In BNF: right-hand side
In BNF: LHS and RHS
Nonterminal
Terminal
pattern matcher for character strings, "front-end". identifies substrings of the source program (lexemes) that belong together
Lexical Analyzer
Syntax Analyzer
Top-down Parser
Bottom-up Parsing
analyze structure of a program through lexical units
Lexical Analyzer
Syntax Analyzer
Top-down Parser
Bottom-up Parsing
invented by John Buckus to describe syntax of Algol 58, is equivalent to cfg
Backus- Naur Form
Context-free grammar
Parse Tree
Attribute Grammars
developed by Noam Chomsky, language generators, used to describe the syntax of natural language
Backus- Naur Form
Context-free grammar
Parse Tree
Attribute Grammars
Regular Grammars
are used to describe tokens
equivalate in power to finite state machines
equivalate in power regular expression
more powerful in cfg
