Форум программистов, компьютерный форум, киберфорум
Haskell
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 5.00/19: Рейтинг темы: голосов - 19, средняя оценка - 5.00
 Аватар для danek130995
33 / 33 / 3
Регистрация: 25.05.2014
Сообщений: 1,137

Написать распознаватели для лексем

13.10.2015, 18:04. Показов 4026. Ответов 36
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Написать следующие распознаватели
1) Слово end
2) Идентификатор
3) Число

Чтобы выдать значение лексемы, нужно воспользоваться оператором <@, с помощью этого оператора можно собрать результат трансляции.

В качестве результата будет значение типа token

Haskell
1
data Token = End | Id String | Num float
Преподаватель на лекции дал вот эти функции:






У меня вопрос на счет функции maybe и just.
Я знаю, как определяется функция maybe:
Haskell
1
2
3
f::Int -> Maybe Int
 f 0 = Nothing
 f x = Just x
Т.е. если пришел не 0, вернет нам это число, иначе ничего не вернет.
В фотографиях лекций есть, например, функция epsilon:
Haskell
1
2
3
4
epsilon :: Parser ()
epsilon xs = Just ((), xs)
type Parser a =
       String -> maybe (a, String)
Как мы узнаем, как определена и работает функция maybe(a, String) для этого случая и как работает Just для некоего кортежа ((), xs)?
Помогите пожалуйста разобраться
1
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
13.10.2015, 18:04
Ответы с готовыми решениями:

Написать анализатор кода, определяющий тип лексем
Допустим есть строка и мне нужно её поделить на точки, запятые, else и так далее, как это сделать на c++ Добавлено через 1 минуту if...

Разработать сканер для выделения лексем из строки текста
Ребят, привет!!! :)Помогите мне пожалуйста... Срочно нужна ваша помощь.:wall: Мне нужно разработать программу – сканер для выделения...

Выделение лексем
Написать программу, использующую механизм управления при помощи таблиц (управление осуществляется данными!). Нужно выделить следующие...

36
Модератор
 Аватар для Curry
5158 / 3484 / 536
Регистрация: 01.06.2013
Сообщений: 7,558
Записей в блоге: 9
13.10.2015, 19:43
Лучший ответ Сообщение было отмечено danek130995 как решение

Решение

Первые буквы идентификаторов в Haskell значимые! Заглавные для Имён модулей, типов, классов, конструкторов ...
Строчные для функций.
Я переписал Ваш конспект, так что заработало. Устал. Вопросы или завтра или не ко мне.
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
module Main where
 
import Prelude hiding((<*>))
import Data.Char
 
type Parser a = String -> Maybe (a,String)
 
--epsilon:: Parser ()
--epsilon xs = Just ( (), xs)
 
symbol _ [] =  Nothing
symbol a (x:xs) 
    | a==x = Just (a,xs)
    | otherwise = Nothing
 
satisfy:: (Char -> Bool) -> Parser Char
satisfy _ [] = Nothing
satisfy p (x:xs)
    | p x = Just (x,xs)
    | otherwise = Nothing
    
infixr 6 <*>
 
(p1 <*> p2) xs = case p1 xs of
                    Nothing -> Nothing
                    Just (y,ys) -> case p2 ys of
                                    Nothing -> Nothing
                                    Just(z,zs) -> Just ((y,z),zs)
 
infixr 4 <|>
 
(p1 <|> p2) xs = case p1 xs of
                    r@(Just _) -> r
                    Nothing -> p2 xs
 
many p xs = case p xs of
                Nothing -> Just ([],xs)
                Just (y,zs) -> Just (y:ys,ws)
                    where Just (ys,ws) = many p zs
 
infixr 5 <@ 
(p <@ f) xs = case p xs of                  
                    Nothing -> Nothing
                    Just(y,ys) -> Just (f y,ys)
        
data Token = End | Id String | Num Int
        deriving Show
 
digit = satisfy isDigit
 
letter = satisfy isAlpha
 
cons (x,xs) = x:xs
 
num = digit <*> many digit  <@ (Num . read . cons)
 
ide = letter <*> many (letter <|> digit) <@ (Id . cons)
 
endWord = symbol 'e' <*> symbol 'n' <*> symbol 'd' <@ (const End)
 
spaces [] =[]
spaces buff@(x:xs)
    | ord x <= 32 = spaces xs
    | otherwise = buff
    
token = endWord <|> ide <|> num  
 
tokens:: String -> [Token]
tokens xs = case (token.spaces) xs of
                Nothing -> []
                Just (tok,ys) -> tok: tokens ys
 
main :: IO () 
main = print $ tokens "qwe45 678 end"
Добавлено через 2 минуты
Старый ghc может ругнуться на строчку 3. Тогда удалите её.
5
 Аватар для danek130995
33 / 33 / 3
Регистрация: 25.05.2014
Сообщений: 1,137
14.10.2015, 19:06  [ТС]
KolodeznyDiver, спасибо огромное за Ваш альтруизм! Будем разбираться, и по ходу задавать вопросы, если можно. 2 недели впереди до сдачи, время есть как следует разобраться. Вся группа Вам безмерно благодарна!
0
5 / 5 / 1
Регистрация: 18.03.2014
Сообщений: 106
21.10.2015, 19:58
KolodeznyDiver, можете, пожалуйста, объяснить, что значат данные выражения:
Haskell
1
2
<*>, <@, infix
import Prelude hiding((<*>))
0
Модератор
 Аватар для Curry
5158 / 3484 / 536
Регистрация: 01.06.2013
Сообщений: 7,558
Записей в блоге: 9
21.10.2015, 20:59
<*> и <@ - это имена функций, которые были определены (придуманы преподавателем). Имена в Haskell могут быть или обычными - из букв, цифр ( _ ') или полностью состоящими из небукв и нецифр. Подробно.
Функция <*> - весьма распространённая стандартная функция, но делающая другое. Она описана (с версии ghci 7.10) в подключаемом по умолчанию модуле Prelude. Т.к. преподаватель решил использовать уже определённое имя, что бы не путаться, я указываю подключение Prelude без функции <*>
Haskell
1
import Prelude hiding((<*>))
(если такие функции, состоящие из значков, не используются в выражении инфиксно (между своими аргументами), то, в остальных случаях, они записываются в скобках.).
Если Вы не указываете import Prelude, то он, всё равно, подключается, полностью.
Haskell
1
infixr 6 <*>
означает, что функции <*> задаётся приоритет 6 и она будет право-ассоциативна (infixl - лево...). https://anton-k.github.io/ru-h... х-операций
2
 Аватар для danek130995
33 / 33 / 3
Регистрация: 25.05.2014
Сообщений: 1,137
21.10.2015, 22:02  [ТС]
KolodeznyDiver, подскажите пожалуйста, что означает запись(для чего служит точка)
Haskell
1
token.spaces
и как работает функция
Haskell
1
just(tok, ys)
? Почему у нее два аргумента? Если я не ошибаюсь, just с одним аргументом просто возвращает то, что в аргументе(Just x вернет x)? Или я ошибаюсь?
0
Модератор
 Аватар для Curry
5158 / 3484 / 536
Регистрация: 01.06.2013
Сообщений: 7,558
Записей в блоге: 9
21.10.2015, 22:52
Цитата Сообщение от danek130995 Посмотреть сообщение
(для чего служит точка
В данном случае (.) - это тоже функция - называется функция композиции
Haskell
1
2
(.)    :: (b -> c) -> (a -> b) -> a -> c
(.) f g = \x -> f (g x)
и выражение (token.spaces) xs можно заменить на token (spaces xs)

Не по теме:

Странно. Это, как если бы Вы изучали си, приводили бы пример аналогичной сложности, и спрашивали "а зачем здесь много знаков = ?"


Цитата Сообщение от danek130995 Посмотреть сообщение
как работает функция just(tok, ys)
Не функция just а конструктор данных Just из типа Maybe. Вы постоянно забываете что Haskell регистрозависимый язык. Если Вы про 71-ую строчку, то Just (tok,ys) - это образец. Если результат Just (кортеж из двух элементов), то их значения будут tok и ys.
А, допустим, в строчке 13 - создать кортеж и "завернуть" его в Just.
2
 Аватар для danek130995
33 / 33 / 3
Регистрация: 25.05.2014
Сообщений: 1,137
21.10.2015, 23:14  [ТС]
KolodeznyDiver,
Цитата Сообщение от KolodeznyDiver Посмотреть сообщение
то их значения будут tok и ys.
Извините, их-это кого? Не совсем понятно..
Что означает
Haskell
1
ord x <= 32
Что такое 32?
0
Модератор
 Аватар для Curry
5158 / 3484 / 536
Регистрация: 01.06.2013
Сообщений: 7,558
Записей в блоге: 9
21.10.2015, 23:28
Цитата Сообщение от danek130995 Посмотреть сообщение
Извините, их-это кого
элементов кортежа.
Цитата Сообщение от danek130995 Посмотреть сообщение
Что такое 32?
Число.
ord - функция из Data.Char возвращающая код символа. 32 - код пробела. Коды всяких табуляций, переводов строки и подобных ещё меньше, а печатаемых символов больше. Выражение ord x <= 32 не очень корректное. В том же Data.Char есть isSpace.
3
 Аватар для danek130995
33 / 33 / 3
Регистрация: 25.05.2014
Сообщений: 1,137
21.10.2015, 23:38  [ТС]
KolodeznyDiver,извините, все время забываю писать с большой буквы конструкторы. То что хаскель-регистрозависимый язык, я помню)

Добавлено через 3 минуты
Цитата Сообщение от KolodeznyDiver Посмотреть сообщение
Если результат Just (кортеж из двух элементов), то их значения будут tok и ys.
не понимаю смысл этой строчки все равно.. Если результат Just -кортеж из двух символов...-вы это имеете ввиду? Тире там имеется ввиду? Или что-то еще?
0
Модератор
 Аватар для Curry
5158 / 3484 / 536
Регистрация: 01.06.2013
Сообщений: 7,558
Записей в блоге: 9
21.10.2015, 23:46
Цитата Сообщение от danek130995 Посмотреть сообщение
Если результат Just -кортеж из двух символов...-вы это имеете ввиду?
да
Цитата Сообщение от danek130995 Посмотреть сообщение
Тире там имеется ввиду?
нет. попробуйте получить результат
Haskell
1
2
3
foo =  case Just (1,2) of
             Just (x,y) -> 10*x+y
             Nothing -> 0
и подумайте
2
 Аватар для danek130995
33 / 33 / 3
Регистрация: 25.05.2014
Сообщений: 1,137
22.10.2015, 12:34  [ТС]
KolodeznyDiver, скомпилировал пример с foo-и кажись разобрался. Just-просто некий кортеж. Позволяет проверить, что пришло два символа(строчка 71), а также упаковать в этот кортеж (строчка 13)

Добавлено через 3 часа 20 минут
KolodeznyDiver, уже начинаю разбираться.. функция spaces убирает пробелы, потом вызывается token xs. Скажите пожалуйста, как работает эта функция? Я вижу
Haskell
1
token = endWord <|> ide <|> num
У меня много догадок, но боюсь они не правильные. Это некое последовательное применение функции <|> к endWord, затем к ide и num и xs? <|> сейчас написана в инфиксном способе записи? Я просто не знаю точно,какие скобки вы имели ввиду -<> или ()?:
Цитата Сообщение от KolodeznyDiver Посмотреть сообщение
в остальных случаях, они записываются в скобках
Знаю, что не правильно написал, поэтому прошу Вас рассказать, как все происходит
0
Модератор
 Аватар для Curry
5158 / 3484 / 536
Регистрация: 01.06.2013
Сообщений: 7,558
Записей в блоге: 9
22.10.2015, 12:50
Цитата Сообщение от danek130995 Посмотреть сообщение
Это некое последовательное применение функции <|> к endWord, затем к ide и num
Да. Если левое применение неудачно, то используется правое. Проанализируйте что делает ф-ия <|>,
её код же есть.
Цитата Сообщение от danek130995 Посмотреть сообщение
<|> сейчас написана в инфиксном способе записи?
В указанном выражении да.
Цитата Сообщение от danek130995 Посмотреть сообщение
Я просто не знаю точно,какие скобки вы имели ввиду -<> или ()?:
(), к примеру, почему две пары скобок в третьей строчке? Внешняя требуется всегда после hiding, а внутреняя относится к самой ф-ии. И так для любой не буквенно-цифровой: 1 + 2 можно записать (+) 1 2.
2
 Аватар для danek130995
33 / 33 / 3
Регистрация: 25.05.2014
Сообщений: 1,137
22.10.2015, 21:18  [ТС]
KolodeznyDiver, если функция <*> -infixr, то она должна начинать выполнение с самого правого конца здесь?
Haskell
1
endWord = symbol 'e' <*> symbol 'n' <*> symbol 'd' <@ (const End)
Т.е. сначала выполнится
Haskell
1
symbol 'd' <@ (const End)
? Но ведь для этого должен выполниться symbol 'd', который принимает два аргумента, а тут то мы один передаем.?
Как в функцию <@ передается xs? Мы когда вызываем token xs вызывается endWord, в котором куда попадает xs? И что такое (const End)?
0
Модератор
 Аватар для Curry
5158 / 3484 / 536
Регистрация: 01.06.2013
Сообщений: 7,558
Записей в блоге: 9
22.10.2015, 22:00
Цитата Сообщение от danek130995 Посмотреть сообщение
если функция <*> -infixr, то она должна начинать выполнение с самого правого конца здесь?
Экспериментируйте. Попробуйте менять infixr на infixl.
Цитата Сообщение от danek130995 Посмотреть сообщение
Как в функцию <@ передается xs?
Последний аргумент, если он ставится в конце выражения, можно опускать, т.е. можно записать более длинно
Haskell
1
endWord xs = (symbol 'e' <*> symbol 'n' <*> symbol 'd' <@ (const End)) xs
В обоих случаях, symbol 'e' <*> symbol 'n' <*> symbol 'd' - это первый аргумент (<@). А теперь посмотрите на реализацию функции (<@), догадайтесь каков тип первого аргумента, и станет понятно как туда попадает xs.

Вообще, полезно будет записать сигнатуры для всех функций. Например,
Haskell
1
symbol :: Eq a => a -> [a] -> Maybe (a, [a])
И так для всех (сигнатура записывается непосредственно перед телом функции). Многое станет понятней.
2
 Аватар для danek130995
33 / 33 / 3
Регистрация: 25.05.2014
Сообщений: 1,137
24.10.2015, 13:27  [ТС]
KolodeznyDiver, Я очень долго размышлял над Вашей программой, многое удалось понять(ну или догадаться), и я все больше и больше поражаюсь ее гениальности.. У меня еще осталось несколько вопросов. Правый аргумент функции <@ -(Id. cons). Я так понимаю, что на вход функции cons идет тоже xs, но в реализации я вижу кортеж (x,xs). Что такое x здесь? А потом к результату применяется Id? Что такое Id здесь?
0
Модератор
 Аватар для Curry
5158 / 3484 / 536
Регистрация: 01.06.2013
Сообщений: 7,558
Записей в блоге: 9
24.10.2015, 14:30

Не по теме:

Цитата Сообщение от danek130995 Посмотреть сообщение
над Вашей программой, ... и я все больше и больше поражаюсь ее гениальности
Это не моя программа. Я её с Вашего конспекта переписал.
И, вообще, я ЭТОГО не люблю.


Цитата Сообщение от danek130995 Посмотреть сообщение
Правый аргумент функции <@ -(Id. cons)
Минуса там нет. <@ (Id . cons) . Кортеж образуется в ф-ии (<*>) , в данном случае, первый символ, выделенный letter и остальных, выделенных по many.
cons, очевидно, объединяет их в одну строку, а Id - один из конструторов данных типа Token. См. стр. 46.

В целом, преподаватель Вам показывает принцип построения парсера в функциональных языках. В полном, рабочем, виде это пакеты parsec, attoparsec и др. Думаю, преподаватель потом про них скажет.
2
 Аватар для danek130995
33 / 33 / 3
Регистрация: 25.05.2014
Сообщений: 1,137
24.10.2015, 15:44  [ТС]
KolodeznyDiver,

Не по теме:

ой, я и забыл про конспект, что это оттуда.


В функции <@ сначала выполняется p xs, где p-вся левая большая часть перед <@(левый аргумент
Haskell
1
letter <*> many (letter <|> digit)
). Если что-то вернулось, тогда выполняется Just(f y, ys), f здесь-это функция cons(пришла в качестве аргумента)? Она вызывается от y, но я не пойму откуда туда второй аргумент попадет(неужели xs?). А конструктор Id что делает?
0
Модератор
 Аватар для Curry
5158 / 3484 / 536
Регистрация: 01.06.2013
Сообщений: 7,558
Записей в блоге: 9
24.10.2015, 16:58
Цитата Сообщение от danek130995 Посмотреть сообщение
f здесь-это функция cons(пришла в качестве аргумента)?
Нет, аргумент (Id . cons), т.е. последовательное применение cons и Id. Id здесь выглядит как функция (вообще, в Haskell конструкторы данных и используются как функции, правда они ещё и в образцах могут быть).
Id просто оборачивает строку чтобы её можно было поместить в список токенов. См. результат main.
Haskell
1
[Id "qwe45",Num 678,End]
Мы не можем в один список поместить и строки, и числа, и пр. Но если все значения - это конструторы данных одного типа (возможно с аргументами) - то всё в порядке. Это список элементов типа Token.
2
 Аватар для danek130995
33 / 33 / 3
Регистрация: 25.05.2014
Сообщений: 1,137
24.10.2015, 22:09  [ТС]
KolodeznyDiver, спасибо большое за ответы, с каждым разом я все ближе к финалу) я не понял, как в cons попадает xs и что это в данном случае будет? Я вижу как вызывается функция f y в <@:Just (f y, ys). ys же не может в нее передаваться, иначе он не был бы записан через запятую
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
24.10.2015, 22:09
Помогаю со студенческими работами здесь

Анализатор лексем
Здравствуйте. Помогите пожалуйста, написать анализатор лексем. Я не понимаю, как он работает в паскале, да и не хочу писать на нём....

Выделение лексем
Приветствую всех! Помогите разобраться с выделением лексем. Необходимо выделить служебное слово (это я сделал сам), а так же восьмеричное...

Порядок лексем
Привет:) Лексический транслятор работает на &quot;тройку&quot;. Вот она: Поле Входные данные - заносим код Паскаля. Поле Выходные данные...

Подсчет лексем
Добрый день! Подскажите пожалуйста, как правильно подсчитать лексемы? Задание: int n = 1; // 5 лексем printf(&quot;Введите...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru