LINUX.ORG.RU
Форум — Development  

Количество токенов нарушающих грамматику

 , ,


0

3

Известно, что с помощью boost::spirit::lex можно распарсить выражение, задав грамматику. Однако, метод tokenize_and_parse(), который предлагается использовать в документации, возвращает только ответ вида «выражение принадлежит грамматике» или «выражение не принадлежит грамматике», останавливаясь на первой лаже. Я же хочу определить количество токенов (они уже были распарсены лексическим анализатором), которые составляют эту лажу. Spirit такое может? Возможно, есть более удачные альтернативы?
PS: возможно, будет понятнее мое желание на примере. Есть SQL запрос: 

 select id,name from database where id=1;
Положим, что он был записан с ошибкой: 
 where id=1 select id,name from database;
Тогда, согласно правилу 
<query specification>    ::=   SELECT [ <set quantifier> ] <select list> <table expression>
можно сказать, что запрос не корректный (что и сделает spirit) и на этом остановиться. А можно сказать, что запрос корректен на, допустим, ~60%, так как всего лишь 4 из 11 токенов стоят не на своем месте.

★

Ответ на: комментарий от sin_a

Да, это, безусловно, возможно. В идеале хотелось бы минимизировать количество нарушителей. То есть, для приведенного мною примера можно также сказать, что 6 последних токенов (без ';') стоят не на своем месте, однако лучше бы сказать, что их четыре (первые четыре) .

maked0n ★
() автор топика

Ты хочешь странного.

anonymous
()
Ответ на: комментарий от maked0n

Похоже, тебе нужно считать расстояние Левенштейна между входящей строкой и строками-образцами. Только в качестве символов будут токены.

Вряд ли Spirit тут поможет

Deleted
()
Ответ на: комментарий от maked0n

может все же flex+bison? Он может так сделать, но все же ты хочешь странного...

aido ★★
()
Последнее исправление: aido (всего исправлений: 1)

Думаю надо гуглить в сторону «fuzzy parsing».

gv ★
()

ты уже какой-то ИИ сюда притянул. это не вопрос парсинга. «процент неправильности» запроса - это какая-то сложная мера, явно не коррелирующая с несовпадениями с шаблоном. да и как юзеру поможет информация, что его запрос «правилен на 37.25%»?

Iron_Bug ★★★★★
()
Ответ на: комментарий от Iron_Bug

да и как юзеру поможет информация, что его запрос «правилен на 37.25%»?

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

Похоже, тебе нужно считать расстояние Левенштейна между входящей строкой и строками-образцами. Только в качестве символов будут токены.

Идея хорошая, только какая-то слишком уж прямолинейная. Если ничего лучше не придумается - так и сделаю. Но пока я подумал, что можно было бы пронумеровать все токены и построить некое синтаксическое дерево. Потом, имея массив (который представляет собой входящий запрос), состоящий из отсортированных номеров-токенов, мы будем пытаться восстановить путь в дереве. Но что-то я не припомню никаких алгоритмов, которые могли бы мне в этом помочь.
PS: я,увы, не мастер ясно излагать свои мысли, так что опять же приведу пример. Пусть есть синтаксическое дерево

1 - 2 - 3 - 5
 \ 
  3 - 4 - 2
Пусть на входе был запрос 135. По-хорошему, нужно бы «восстановить» маршрут 1235 (пользователь просто пропустил токен 2), но если делать «в лоб» (то есть просто спускаться, пока символы совпадают), то восстановится 1342. Может быть уважаемое сообщество подскажет, есть ли какие-нибудь подобные алгоритмы на графах?

maked0n ★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development