4

我在这里得到了这段代码，它是一个用 Haskell 结构的命令式编程语言编写的程序，所以问题是“我怎样才能为这种语言实现词法分析器和解析器”，程序被定义为一个序列语句有 6 种类型：“:=”、“goto”、“write”、“stop”、“if goto”和“int”

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

我有点迷路了，我读过关于词法分析器和解析器的文章，但没有找到任何如何实现它们的例子，如果你能给我一段代码，我将不胜感激，这样我就可以自己尝试做，或者至少有有用信息的链接

4

1 回答 1

24

开始使用 Parsec 进行解析

我不会为你写完整的东西，但我会让你从每一点开始。我们将经历的三个阶段是：

  1. 定义语法
  2. 制作抽象语法树。（这看起来像语法，所以很容易。）
  3. 编写解析器。（这也看起来像语法，所以很容易。）

我们可以在 2 和 3 之间建立一个单独的词法分析阶段，但是 Parsec 很乐意同时做这两个级别。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 语句很不寻常，因为其中没有=or ==。也许这是为了简化语法，它只能接受单个变量或整数，之间有空格。也许这是一个错字，你的意思是有一个等号和任意表达式。找出哪个并重写ifstatement语法的一部分。

第 6 行的赋值很复杂，因为在这里你必须解析任意算术表达式。据我记得有很多这样的例子，所以我现在很乐意跳过它。如果你被那一点卡住了，那就另当别论了，但希望你能先用剩下的部分建立你的解析技能。

2.抽象语法树（AST）

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

我实际上正在编译这个答案（一种检查拼写错误等的好方法），这就是为什么我需要在代码顶部进行一些声明：

module ParseLang where

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

我们将只创建一个sProgram列表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

我们使用了 ，这是我们通过导入获得<$>的同义词。在这里，它使用左侧的纯函数更改解析器返回的值，在本例中为. 如果您不习惯，请查看此其他答案以进行介绍。fmapControl.Applicativereadfmap

让我们做一个解析器来解析字符串文字然后是一些空格：

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

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

现在这<*很有趣。它看起来像<*>，它实际上结合了两个解析器，并与它一起使用<$>，实际上将纯函数映射到结果上。*>并<*结合两个解析器，但忽略其中一个的输出，因此string "goto" <* whitespace解析 a"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 VarNameorInt而不是 general 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"
于 2012-12-05T03:55:27.423 回答