Lexical Analysis and Parsing
For complex symbolic notations, such as programming languages, conversion of the textual representation of a program into an internal abstract syntax form often involves an intermediate step of lexical analysis prior to the actual parsing process.
Lexical Analysis: White Space, Comments and Tokens
The grammar of programming languages is often described without explicit reference to the white space (space and tab characters, carriage returns, line feeds, etc.) that may separate the significant tokens of the language. Furthermore, it is often convenient to simplify the task of the parser by explicitly forming tokens from the input ahead of time. Most often, tokens are those that can be identified as instances of particular regular expressions. The process of lexical analysis is often called tokenization and the lexical analyzer itself may be called a tokenizer.
For example, for the domain of Small Lisp, the regular expressions that are useful for tokenization are the following:
comment: (^;;;.*$)+
numeral: -?[0-9]+
alphanumeric_symbol: [A-Za-z](-?[A-Za-z0-9])*
special_symbol: [-+*/<>=&|!@#$%?:]+
lparen: \(
rparen: \)
lbrak: \[
rbrak: \]
lbrace: \{
rbrace: \}
equal: =
semicolon: ;
arrow: -->
quote-mark: "
colon: :
We can represent these tokens using a Haskell algebraic data type.
data Token = Comment [Char] |
Numeral Int |
AlphaNum [Char] |
Special [Char] |
Lparen | Rparen | Lbrak | Rbrak | LBrace | RBrace
Equal | Semicolon | Arrow | Quote | Colon
Most often tokenization follows the longest-match rule: tokens are formed from the left taking the longest possibly string that matches the given regular expression, while not consuming any whitespace.
For example, the Small Lisp definition
make-negation[expr] = list2["-"; expr]
could be represented using the following Haskell [Token] value.
[AlphaNum "make-negation", Lbrak, AlphaNum "expr", RBrak, Equal, AlphaNum "list2", Lbrak, Quote, Special "-", Quote, Semicolon, AlphaNum "expr", RBrak]
Question: Why don't you expect to see token streams such as the following?
[AlphaNum "make", Special "-", AlphaNum "negation"]
The Tokenizer
How do you write a tokenizer? Below we show how a tokenizer for the Small Lisp programming language can be written in Haskell.
However, it is possible to consider automatically generated tokenizers. The idea is to define the tokens of a language using regular expressions (as above). Then a special symbolic computing application called a lexical-analyzer generator can be used. Such an application would automatically build a lexical analyzer from the given set of regular expressions. An example is the program Flex.
However, writing a lexical analyzer by hand is not conceptually difficult and may sometimes be necessary for various reasons. One reason is there may be ambiguities in token syntax that are not handled by the regular expression given. Another is that there may be special white-space or comment rules.
Small Lisp does have some complexity for lexical analysis.
One issue is that some tokens are ambiguous: the - (Equal), --> (Arrow)
and : (Colon) tokens are also legal as Special tokens. Another is that the syntax of Small Lisp comments
is somewhat unusual.
Now consider the following Small Lisp tokenizer. We design
it to produce a tokenization of any input stream, without
wrapping the result in a Maybe type. Instead we
introduce a BadToken constructor to represent illegal
input tokens.
module SmLispTokenize where
import Data.Char
data Token = Comment [Char] |
Numeral Int |
AlphaNum [Char] |
Special [Char] |
Lparen | Rparen | Lbrak | Rbrak | LBrace | RBrace |
Equal | Semicolon | Arrow | Quote | Colon |
BadToken Char deriving Show
tokenize [] = []
tokenize ('\n': ';' : ';' : ';' : more_chars) =
let (rest_of_line, more_lines) = span (/='\n') more_chars
in (Comment rest_of_line): tokenize more_lines
tokenize (' ':more) = tokenize more -- skip white space
tokenize ('\n':more) = tokenize more -- skip white space
tokenize ('(':more) = Lparen: (tokenize more)
tokenize (')':more) = Rparen: (tokenize more)
tokenize ('[':more) = Lbrak: (tokenize more)
tokenize (']':more) = Rbrak: (tokenize more)
tokenize ('{':more) = LBrace: (tokenize more)
tokenize ('}':more) = RBrace: (tokenize more)
tokenize (';':more) = Semicolon: (tokenize more)
tokenize ('"':more) = Quote: (tokenize more)
tokenize t@(c:more)
| isAlpha c = getAlphaNum [c] (span isAlphaNum more)
| isDigit c = getNumToken (digitToInt c) more
| otherwise = getSpecial (span (\c -> elem c "+-*/<>=&|!@#$%?:") t)
getSpecial ("", (c : more)) = BadToken c : (tokenize more)
-- Note: the following tokens may also be used as symbolic atoms;
-- the parser must recognize this situation
getSpecial ("=", more) = Equal : (tokenize more)
getSpecial ("-->", more) = Arrow : (tokenize more)
getSpecial (":", more) = Colon : (tokenize more)
getSpecial ("-", c:more)
| isDigit c = let (Numeral n:tokens) = getNumToken (digitToInt c) more
in (Numeral (-n)): tokens
| otherwise = (Special "-") : (tokenize (c:more))
getSpecial (specials, more) = (Special specials) : (tokenize more)
getNumToken accum [] = [Numeral accum]
getNumToken accum (c:more)
| isDigit c = getNumToken (accum * 10 + (digitToInt c)) more
| otherwise = Numeral accum : (tokenize (c:more))
getAlphaNum pfx (alphanum, s@('-':c:more))
| isAlphaNum c = getAlphaNum (pfx ++ alphanum ++ ['-',c]) (span isAlphaNum more)
| otherwise = AlphaNum (pfx ++ alphanum) : (tokenize s)
getAlphaNum pfx (alphanum, more) = AlphaNum (pfx ++ alphanum) : (tokenize more)
One issue to consider in this tokenizer is the recognition of comment lines. Under what circumstances may the tokenizer fail to correctly recognize a comment? How could that be handled?
Parsing from Token Streams
Given token streams, parsing functions have a slightly different type signature than when working with character strings directly. To parse Small Lisp programs, the main parsing functions would handle the three prinicipal subdomains.
parseSExpression :: [Token] -> Maybe (SExpression, [Token]) parseSmLispExpr :: [Token] -> Maybe (SmLispExpr, [Token]) parseSmLispProgram :: [Token] -> Maybe (SmLispProgram, [Token])
Parsing Small Lisp values: S-expressions
Our first parsing function handles Small Lisp values (S-expressions)
parseSExpression :: [Token] -> Maybe (SExpression, [Token])
parseSExpression (Numeral n: tokens) = Just (NumAtom n, tokens)
parseSExpression (AlphaNum s: tokens) = Just (SymAtom s, tokens)
parseSExpression (Special s: tokens) = Just (SymAtom s, tokens)
parseSExpression (Arrow: tokens) = Just (SymAtom "-->", tokens)
parseSExpression (Equal: tokens) = Just (SymAtom "=", tokens)
parseSExpression (Colon: tokens) = Just (SymAtom ":", tokens)
parseSExpression (Lparen: tokens) = parseSExpressionList [] tokens
parseSExpression _ = Nothing
parseSExpressionList exprs (Rparen : more) = Just (List exprs, more)
parseSExpressionList exprs tokens =
case parseSExpression tokens of
Just (e, more) -> parseSExpressionList (exprs ++ [e]) more
_ -> Nothing
Parsing Small Lisp Expressions
type Identifier = [Char]
data SmLispExpr = SExpr SExpression |
Variable Identifier |
FnCall Identifier [SmLispExpr] |
CondExpr [CondClause] |
LetExpr [LocalDef] SmLispExpr deriving Show
data CondClause = Clause SmLispExpr SmLispExpr deriving Show
data LocalDef = Binding Identifier SmLispExpr deriving Show
parseSmLispExpr :: [Token] -> Maybe (SmLispExpr, [Token])
parseSmLispExpr (Lbrak : tokens) = parseCondExpr [] tokens
parseSmLispExpr (LBrace : tokens) = parseLetExpr [] tokens
parseSmLispExpr (AlphaNum s: Lbrak : tokens) = parseFnCall s [] tokens
parseSmLispExpr (AlphaNum s: tokens) = Just (Variable s, tokens)
parseSmLispExpr (Quote : t : Quote : tokens) =
case parseSExpression [t] of
Just (SymAtom s, []) -> Just (SExpr (SymAtom s), tokens)
_ -> Nothing
parseSmLispExpr tokens =
case parseSExpression tokens of
Just (List s, more) -> Just (SExpr (List s), more)
Just (NumAtom n, more) -> Just (SExpr (NumAtom n), more)
_ -> Nothing
parseCondExpr clauses tokens =
case parseSmLispExpr tokens of
Just (e, Arrow: more) ->
case parseSmLispExpr more of
Just (rslt, Semicolon:yet_more) ->
parseCondExpr (clauses ++ [Clause e rslt]) yet_more
Just (rslt, Rbrak:yet_more) ->
Just (CondExpr (clauses ++ [Clause e rslt]), yet_more)
_ -> Nothing
_ -> Nothing
parseFnCall s args tokens =
case parseSmLispExpr tokens of
Just (e, (Semicolon:more)) -> parseFnCall s (args ++ [e]) more
Just (e, (Rbrak:more)) -> Just (FnCall s (args ++ [e]), more)
_ -> Nothing
parseLetExpr defs (AlphaNum s: Equal: tokens) =
case parseSmLispExpr tokens of
Just (e, Semicolon:more) ->
parseLetExpr (defs ++ [Binding s e]) more
Just (e, Colon:more) ->
case parseSmLispExpr more of
Just (e2, RBrace:yet_more) ->
Just (LetExpr (defs ++ [Binding s e]) e2, yet_more)
_ -> Nothing
_ -> Nothing
parseLetExpr defs tokens = Nothing
Parsing Small Lisp Programs (Lists of Definitions)
data Definition = ConstantDef Identifier SmLispExpr |
FunctionDef Identifier [Identifier] SmLispExpr deriving Show
parseSmLispProgram [] = Just []
parseSmLispProgram (Comment t: more) = parseSmLispProgram more
parseSmLispProgram (AlphaNum name: Equal : more) =
case parseSmLispExpr more of
Just (e, yet_more) ->
case parseSmLispProgram yet_more of
Just p -> Just ((ConstantDef name e): p)
_ -> Nothing
_ -> Nothing
parseSmLispProgram (AlphaNum name: Lbrak : AlphaNum arg : more) =
case parseArguments [arg] more of
Just (args, Equal: yet_more) ->
case parseSmLispExpr yet_more of
Just (e, further_more) ->
case parseSmLispProgram further_more of
Just p -> Just ((FunctionDef name args e): p)
_ -> Nothing
_ -> Nothing
_ -> Nothing
parseSmLispProgram _ = Nothing
parseArguments args (Rbrak : more) = Just (args, more)
parseArguments args (Semicolon: AlphaNum a: more) =
parseArguments (args ++ [a]) more
parseArguments _ _ = Nothing
parseExpressionText srctxt =
case parseSmLispExpr (tokenize srctxt) of
Just (e, []) -> Just e
_ -> Nothing
parseProgramText srctxt = parseSmLispProgram (tokenize ('\n':srctxt))