Продолжение lex после обнаружения ошибки

Я прохожу курс компиляторов в моем университете. Я предпочитаю делать проект с использованием Haskell + Parsec. Лексер и синтаксический анализатор должны быть отдельными. Я использую Parsec для преобразования строки в список токенов, который затем будет передан другому парсеру Parsec, который преобразует список токенов в AST.

Проблема в том, что лексер должен продолжать попытки лексирования даже в случае ошибки. Чтобы попытаться сделать это, я ввел токен, представляющий «неожиданный токен», в мой тип данных Token, и я попытался добавить в свой код <|> неожиданно, чтобы создать этот токен в случае ошибки. Это много шаблонов, и также может быть сложно понять, где их разместить.

Я предпочел бы каким-то образом сделать так, чтобы Parsec автоматически делал это: если когда-либо возникает ParseError, генерировать неожиданный токен в этой позиции и продолжать синтаксический анализ одной позиции позже. Как бы я это сделал?

Вот фрагмент кода, который у меня есть сейчас: http://lpaste.net/8144414997276000256 По какой-то причине Я все еще могу получить ошибку синтаксического анализа, даже если токен Unexpected должен улавливать необработанные случаи.


haskell parsec
person Diony Rosa    schedule 12.09.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Похоже, вы сможете обойтись одним лишним unexpected термином. Я предполагаю, что у вас есть тип token, который выглядит примерно так:

token' =  number
      <|> identifier
      <|> ...

Я бы, вероятно, попросил каждый токен (number, _5 _... и т. Д.) Управлять своим собственным пробелом:

number :: Parser Token
number = Number . read <$> many1 digit <* spaces

Почему бы не добавить неожиданный термин в конце в качестве универсального?

token' =  number
      <|> identifier
      <|> ...
      <|> unexpected'

Пусть он поглотит одного персонажа. Для улучшения сообщений об ошибках вы даже можете включить символ в значение. Затем, когда вы используете это для создания списка, вы получите значение Unexpected для каждого символа, с которым ваш лексер не знает, что делать.

unexpected' :: Parser Token
unexpected' = Unexpected <$ anyChar

Наконец, весь lex - это просто many token'. В моих тестах это нормально работает с недопустимыми символами в середине.

*Main> parse (many token') "<foo>" "1 2 abc ~ ~def"
Right [Number 1,Number 2,Identifier "abc",Unexpected,Unexpected,Unexpected,Identifier "def"]

Следует иметь в виду, что Parsec не выполняет возврат по умолчанию. Это означает, что если синтаксический анализ не удастся частично выполнить токен, он не вернется и вместо этого попробует unexpected: вы просто получите сообщение об ошибке. Чтобы включить отслеживание с возвратом, вы должны использовать try в синтаксическом анализаторе, который может вызвать ошибку. Например, если identifier требуется два символа:

identifier :: Parser Token
identifier = Identifier <$> liftA2 (:) letter (many1 alphaNum) <* spaces

Тогда он может не пройти часть пути и не вернуться назад. Но если обернуть его в try, он должен работать:

token' =  number
      <|> try identifier
      <|> ...

Проблема с try в том, что он может замедлить ваш код, если вы не будете осторожны. Однако, если вы не возражаете против замедления, возможно, вам удастся просто добавить try повсюду и много возвращаться!

person Tikhon Jelvis    schedule 12.09.2014
comment
Вот фрагмент моего кода. Я создаю свой анализатор токенов, складывая их ‹|›, как и ваш токен ' example, но каким-то образом возникает ошибка синтаксического анализа, хотя синтаксический анализатор должен в конечном итоге попробовать синтаксический анализатор Unexpected. - person Diony Rosa; 13.09.2014
comment
@DionyRosa: Возможно, дело в том, что try не используется в нужных местах. Я немного об этом к ответу. - person Tikhon Jelvis; 13.09.2014
comment
Спасибо! После того, как я действительно не понимал разницы между попыткой и ‹|› до этого - person Diony Rosa; 16.09.2014