Summary
Summary of the course Languages and Compilers (Talen en Compilers)
- Course
- Institution
Summary of the course 'Languages and Compilers' at Utrecht University, based on the lectures and lecture notes of the teacher.
[Show more]
1 review
By: stormluykx • 10 months ago
Seller
Follow
pactasuntservanda
Reviews received
Content preview
Languages, compilers and (context-free) grammarsWhat is a compiler and a parser?
A compiler translates one language into another (which is possibly the same), roughly:
Get hold of the structure of the input program attach semantics to a sequence of symbols check whether a program
makes sense optimize generate good machine code.
A parser takes a string of characters and tries to recognize a structure in the form of a tree.
Alphabet, languages and words
An alphabet is a (finite) set of symbols that can be used to form sentences, e.g.
The set of all Latin letters
Given such a set, we can consider (finite) sequences of elements of that set (in which the empty sequence is often written
as ). The set of sequences of a given set is written as and defined as:
the empty sequence is in .
if and , then is in .
(We typically use letters from the beginning of the (Latin) alphabet to represent single symbols, and letters from the end of
the alphabet to represent sequences.)
A word is a sequence of symbols from the alphabet. A language is a set of "correct" sentences of words. Thus, a language
is a subset of .
Grammars
Languages can be defined using inductive definitions, represented formally by making use of deduction rules.
Rule Meaning
If … and are true, then is true
is true (= axiom)
Grammars are a shorthand way to define a language inductively, by means of rewrite rules called productions (instead of
deduction rules). A grammar consists of multiple productions (e.g. in the grammar of palindromes).
Symbols from the alphabet are also called terminals in a grammar.
, The grammar makes use use of auxiliary symbols called nonterminals, that are not part of the alphabet and hence
cannot be part of the final word/sentence. (e.g. in the example production above.)
Starting from a nonterminal, we can rewrite successively until we reach a string of terminals. Such a sequence
is called a derivation.
A nonterminal could be a start symbol, often denoted as . (Context-free grammars have only one start
symbol.)
Note that not all languages can be generated/described by a grammar. On the other hand, multiple grammars may describe
the same language in which case these grammars are equivalent.
Context-free grammars
Grammars where the left hand side of a production always consists of a single nonterminal are called context-free
grammars. Languages that can be described by context-free grammar are called context-free languages.
A context-free grammar is a four-tuple , where:
is a finite set of terminal symbols.
is a finite set of nonterminal symbols.
is a finite set of production rules, each of form , where is a nonterminal and is a sequence of terminals
and nonterminals.
is the start symbol, .
Because context-free languages are relatively easy to deal with algorithmically, most programming languages are context-
free languages.
BNF (Backus Naur Form) and EBNF
Instead of writing every production on a single line, we may rewrite any number of rewrite rules for one nonterminal using a
shorthand notation called BNF, by using the symbol. e.g.:
can be combined to: .
Extended BNF (EBNF) is introduced to help abbreviate a number of standard constructions that usually occur often in the
syntax of a programming language:
and/or , means one or zero occurrences of nonterminal (i.e. optional).
, means one or more occurrences of nonterminal .
and/or , means zero or more occurrences of nonterminal .
These notations can be used for languages, grammars, nonterminals and sequences of terminal and nonterminal symbols.
, The language of a grammar
The language of a grammar , usually denoted , is defined as
Parse trees and ambiguity
We can visualize a derivation as a parse tree (a.k.a. abstract syntax tree (AST)). For example, for the grammar
the following derivation has the following parse tree:
The set of all equivalent derivations can be represented by selecting a so-called canonical element. A good candidate for
this element is the leftmost derivation. In a leftmost derivation, the leftmost nonterminal is rewritten in each step. (This is
not the case in the example above.)
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller pactasuntservanda. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.64. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
56326 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now