Проблема с рекурсией, пишущей крошечный парсер в Haskell. Проверьте переменные - PullRequest
Новая
       31

Проблема с рекурсией, пишущей крошечный парсер в Haskell. Проверьте переменные

0 голосов
/ 08 октября 2009

Я все еще работаю над крошечным парсером для крошечного языка, определенного в школьном задании. Парсер, который генерирует AST (Абстрактное синтаксическое дерево), работает. Я хочу проверить определенные переменные, они должны быть ограничены выражением let. Сначала метод, который определен в задаче (предложение не требуется): 

checkVars :: Expr -> Char 

data Expr =  Var Char | Tall Int | Sum Expr Expr | Mult Expr Expr | Neg Expr | Let Expr Expr Expr
    deriving(Eq, Show)

Допустимое предложение: «пусть X будет 5 в * (2, X)». X обычно представляет собой Var, а 5 обычно представляет собой int. И последний может быть любой частью типа dataExpr. Основная точка: X используется где-то в последнем выражении. Тип данных для let: 

Let Expr Expr Expr

Ссылка на другие вопросы, которые я задавал об этой задаче, здесь только к вашему сведению; Первый вопрос Второй вопрос

Как вы видите, тип данных для checkVars - это Expr, поэтому вот пример того, что я бы передал этой функции: 

parseProg "let X be 4 in let Y be *(2 , X) in let Z be +(Y , X) in
+(+(X , Y) , Z)"
Let (Var 'X') (Tall 4) (Let (Var 'Y') (Mult (Tall 2) (Var 'X')) (Let
(Var 'Z') (Sum (Var 'Y') (Var 'X')) (Sum (Sum (Var 'X') (Var 'Y')) (Var
'Z'))))
Just 24

Это всеобъемлющий пример, верхняя часть - строка / программа, которая анализируется. Вторая часть, начинающаяся со строки 3 (Let), представляет собой AST, вход для функции checkVars. А нижняя часть «Просто 24» - это оценка. Для которого я вернусь сюда за дополнительной помощью. Примечание. Смысл в том, чтобы выложить первую несвязанную переменную, найденную как ошибку, и '', если все в порядке. Очевидно, что если вы хотите сделать это по-другому, вы можете.

Ответы [ 2 ]

5 голосов
/ 08 октября 2009

Вот о чем подумать:

Первое поле вашего конструктора Let - это Expr. Но может ли он содержать что-то еще, кроме Var с? Если нет, вы должны отразить это, сделав тип этого поля, скажем, String и соответствующим образом адаптировать анализатор. Это значительно облегчит вашу задачу.

Стандартный трюк для вычисления выражения с привязками let (что вы делаете) - написать функцию 

type Env = [(String, Int)]
eval :: Expr -> Env -> Int

Обратите внимание на дополнительный аргумент для среды. Среда отслеживает, какие переменные в любой момент времени связаны с какими значениями. Его позиция в типе означает, что вы можете определять его значение каждый раз, когда вызываете eval для дочерних выражений. Это очень важно! Это также означает, что вы можете иметь локально объявленные переменные: привязка переменной не влияет на ее контекст, только на подвыражения.

Вот особые случаи:

  • В Var вы хотите lookup имя переменной в среде и вернуть значение, связанное с ней. (Используйте стандартную функцию прелюдии lookup.)
  • В Let вы хотите добавить дополнительный (varname, value) в начало списка среды перед передачей его дочернему выражению.

Я пропустил некоторые детали, но этого должно быть достаточно, чтобы вы проделали долгий путь. Если вы застряли, задайте еще один вопрос. : -)

О, и я вижу, что вы хотите вернуть значение Maybe, указывающее на ошибку. Я предлагаю вам сначала попробовать без и использовать error, чтобы указать несвязанные переменные. Если у вас работает эта версия eval, адаптируйте ее так, чтобы она возвращала значения Maybe. Причина этого в том, что работа со значениями Maybe делает оценку немного более сложной.

0 голосов
/ 08 октября 2009

Я бы на самом деле попытался оценить AST. Начните с обработки (и, следовательно, удаления) всех Let s. Теперь попробуйте оценить полученный AST. Если вы столкнетесь с Var, тогда появится несвязанная переменная.

...