如何在Haskell中实现词法分析器和解析器

Question

我在这里得到了这段代码,它是一个用Haskell构造的命令式编程语言编写的程序,所以问题是"如何为这种语言实现词法分析器和解析器",该程序被定义为一个序列其中有6种类型的语句:":=","goto","write","stop","if goto"和"int"

1. int n = 5
2. 写
3. int fac = 1
4. if0 n转到8
5. fac:= fac*n
6. n:= n-1
7. 转到4
8. 写fac
9. 停

我有点迷失在这里,我读过有关词法分析器和解析器的内容,但是没有找到任何示例如何实现它们,如果你能给我一段代码我会很感激,所以我可以尝试自己做,或者至少链接有用的信息

Answer 1

开始使用Parsec进行解析

我不会为你写完整件事,但我会让你从头开始.我们要经历的三个阶段是:

1. 定义语法
2. 制作抽象语法树.(这看起来像语法,所以很容易.)
3. 写一个解析器.(这也看起来像语法,所以很容易.)

我们可以在2到3之间做一个单独的lexing阶段,但Parsec乐意做两个级别.Lexing是将输入分成标记的地方 - 有意义的输入位 - 相当于人类语言中的单词,也称为lexemes.跳过一个单独的lexing阶段意味着我们需要对空白等更加明确.

1.语法

首先,您需要定义语法.最好用纸和笔,但我会让你开始:

  program ::= line {[newline line]}
  line ::= num dot whitespace statement
  statement ::= declaration | write | ifstatement | goto | assignment | stop
  declaration = "Int" whitespace varname equals int
  varname = letter {[alphanum]}
  -- more things here, including the more interesting ifstatement:
  ifstatement = "if" whitespace expression whitespace equals expression whitespace statement


  -- lower level stuff:
  dot = "."
  int = digit {[digit]}
  digit = "0" | "1" | ...  | "9"
  whitespace = " " okspace | "\t" okspace
  okspace = "" | whitespace

考虑一下如何匹配您的示例程序,并考虑如何完成它:

1. Int n=5
2. write n
3. Int fac=1
4. if 0 n goto 8          -- unusual
5. fac := fac * n
6. n := n+1               -- complex
7. goto 4
8. write fac
9. stop

第4行中的if语句不常见,因为没有=或==在其中.也许这是为了简化语法,它只能接受单个变量或整数,两者之间有空格.也许这是一个错字,你的意思是有一个等号和任意表达.找出哪些并重写ifstatement语法的一部分.

第6行中的赋值很复杂,因为在这里你必须解析任意算术表达式.据我所知,有很多例子可以解决,所以我现在很乐意跳过这个例子.如果你对这个问题感到困惑,那就另外提出一个问题吧,但希望你能先用其余的东西建立你的解析技巧.

2.抽象语法树(AST)

抽象语法树表示构成输入的标记组合.在Haskell中,我们可以定义自己的内容以适应上下文,这将使生活更简单

我实际上正在编译这个答案(检查拼写错误等的好方法),这就是为什么我需要在代码顶部的一些声明:

module ParseLang where

import Text.Parsec hiding (Line)
import Text.Parsec.String
import Control.Applicative hiding ((<|>), many)

我们只是创建一个s Program列表Line,但是在解析器中强制执行必须至少有一个.

type Program = [Line]

对于a Line,它需要一个数字和一个语句,但点只是我们不需要存储的语法.我们可以将行号存储为Int,因此尽管在类型声明中允许使用负数,但解析器也不会接受否定号.

data Line = Line {aNum::Int, aStatement :: Statement} 
   deriving Show

多个选项很容易定义:

data Statement = Declaration VarName Int
               | Write VarName
               | IfStatement Expression Expression Statement
               | Goto LineNumber
               | Assignment VarName Expression
               | Stop
   deriving Show

注意缺少所有语法cruft/connectives /等号只留下改变的位.

我停在那里 - 你可以完成:

data Expression = Expression -- I've left this one for you
   deriving Show

type VarName = String   -- could use newtype for type safety for these to
type LineNumber = Int   

较低级语法不需要在AST中表示,因为我们将使用字符串.

3.解析器

这一点现在很好,很容易.让我们从语法树的底部开始并进行处理.

num :: Parser Int
num = read <$> many digit

我们使用过<$>,这是fmap我们通过导入获得的同义词Control.Applicative.在这里,它使用左侧的纯函数更改解析器返回的值,在本例中read.如果您不习惯,请查看其他答案以获得介绍fmap.

让我们创建一个解析器,解析字符串文字然后解析一些空格:

whitespace = space >> spaces  -- a space then optional spaces

lit :: String -> Parser String
lit xs = string xs <* whitespace

现在这<*很有趣.看起来<*>,它实际上组合了两个解析器,并且<$>实际上将纯函数映射到结果上.*>并<*结合两个解析器,但忽略其中一个解析器的输出,所以string "goto" <* whitespace解析一个"goto"和一些空格,但扔掉空白.

现在我们准备解析一个goto语句:

goto :: Parser Statement
goto = Goto <$> (lit "goto" *> num)

现在让我们来看看varName

varName :: Parser VarName
varName = (:) <$> letter <*> many (alphaNum <|> oneOf "'_")

那里有几件事情正在发生.

1. <|>替代选择 - 一个或另一个,所以(alphaNum <|> oneOf "'_")接受一个字母数字字符或那对无辜字符中的一个',_你可能想要包含在变量名称中.

2. f <$> parser1 <*> parser2是一种非常好的组合解析器的方法.它运行parser1,然后运行parser2,然后将函数映射f到它们生成的结果f上.它适用于许多解析器:

--ifstatement = "if" whitespace expression whitespace equals whitespace expression whitespace statement
ifStatement :: Parser Statement
ifstatement = IfStatement 
          <$> (lit "if" >> expression) 
          <*> (lit "=" >> expression)    -- I put = in, but see below
          <*> (whitespace >> statement)  -- I'd be happier with a then in here

如果你只允许a VarName或Int代替一般Expression,那么你不需要等号.

这是你如何把它放在一起:

statement :: Parser Statement
statement = goto
        <|> stop
        <|> declaration 
        <|> write
        <|> ifStatement
        <|> assignment


--program ::= line {[newline line]}
program :: Parser Program
program = many1 line


--line ::= num dot whitespace statement
line :: Parser Line
line = Line <$> (num <* char '.') <*> (statement <* char '\n')

但是每次尝试使用尚未完成的解析器时,我都会给你留下错误消息,所以整个过程都会编译好,你定义的位应该可以工作.

stop =        error "You've not yet defined stop"
declaration = error "You've not yet defined declaration"
write =       error "You've not yet defined write"
ifStatement = error "You've not yet defined ifStatement"
assignment =  error "You've not yet defined assignment"
expression =  error "You've not yet defined expression"