Lecture 2: Syntax & Parsing

목차

 

Learning Objectives

Understand what grammars are 

Write your own grammars from a specification

Know what Algebraic Data Types are

Define your own Algebraic Data Types (in Scala)

Apply pattern matching in (Scala) programs

Create abstract syntax tree from programs given a grammar (EXAM QUESTION)

Know what s-expressions are

Write simple parsers

 

 

Syntax

 

Syntax: the structure of program phrases in a language

Semantics: the meaning of a program

Abstraction: a feature of a programming language which allows a certain type of expression.

A grammar describes the syntax of a language

Syntax defines what your abstraction looks like

 

 

Grammars

BNF Grammar

 

E is a number and they can add and multiply.

BNF grammars tend to be very imprecise

 

 

Context-Free Syntax (SDF)

The recipe for parsing and disambiguation (명확화)

 

 

Lexical syntax (SDF)

The shape of the lexemes / words / tokens of a language

 

Abstract Syntax Tree

The abstract syntax of a program represents its structure and abstracts from irrelevant syntactic details.

AST: A tree structure for representing programs, which abstracts from irrelevant syntactic details. It removes the irrelevant syntactic details and leaves a tree as a convenient representation to give meaning to a program.

 

 

 

 

AST Flat Form

 

 

얘는 (1 + (2 * 3) ) + (4 * 5)

 

 

Algebraic Data Types

Algebraic Data Type: Inductive definition of a type formed by combining other types, in a way that allows one to do pattern matching. E.g. Records in Java and case classes in Scala

 

 

 

 

Inductive Definitions

 

 

Example

 

 

Pattern Matching Example

 

Pattern Matching: An abstraction in programming languages which allows you to match structurally to input terms (ADTs), and define behaviors depending on the shape or content of the input.

S-Expressions

 

 

 

S-Expression Parsing