Справка по регулярному выражению для идентификатора в лексическом анализаторе

Я пытаюсь создать лексер, я не хочу использовать файл lex, потому что хочу учиться, поэтому перейдем к тому, что я хочу создать регулярное выражение для идентификатора со следующими ограничениями:

'__' не может быть идентификатором. подчеркивание всегда с какой-либо буквой. Id содержит хотя бы одно подчеркивание. Подчеркивание не может быть последним символом идентификатора.
Должен содержать одну или несколько цифр. Не начинать с цифры.

Теперь регулярное выражение, которое я сделал до сих пор:

([_a-zA-Z]*[a-zA-Z][a-zA-Z]*[_a-zA-Z]*[0-9][0-9]*[_a-zA-Z]*)*

Проблема в том, что я не могу выполнить ограничение «по крайней мере один _» в идентификаторе, я не могу сделать его более сложным, потому что мне нужно преобразовать это регулярное выражение в недетерминированный конечный автомат, поэтому не могли бы вы помочь.


regex compiler-construction lexer regular-language computation-theory
person Community    schedule 01.10.2015    source источник
comment
только что отредактировал мое описание   -  person    schedule 01.10.2015
comment
Требовать хотя бы одну букву А в строке несложно: просто скажите [AB]*A[AB]*. И все регулярные выражения могут быть преобразованы в NFA и DFA — здесь вы не используете какие-либо функции регулярных выражений, которые сделали бы ваш язык нерегулярным.   -  person Kilian Foth    schedule 01.10.2015
comment
да, я знаю, но, как вы можете видеть, есть и другие ограничения, связанные с подчеркиванием, теперь R.A немного сложен, и я не могу найти его место, где я должен разместить подчеркивание внутри или где я должен разместить повторяющийся путь   -  person    schedule 01.10.2015
comment
Просто к вашему сведению, XX* можно сократить до X+ (этот шаблон можно найти дважды в вашем регулярном выражении).   -  person sp00m    schedule 01.10.2015
comment
Что именно вы подразумеваете под подчеркиванием всегда с какой-то буквой? Вы имеете в виду, что за каждым символом подчеркивания должна следовать буква? Или вы имеете в виду, что каждое подчеркивание должно либо следовать за буквой, либо сопровождаться буквой?   -  person rici    schedule 01.10.2015
comment
В общем, если вы строите конечный автомат вручную, вероятно, проще нарисовать схему железной дороги чем работать с регулярным выражением, а затем преобразовывать его обратно в переходы между состояниями.   -  person rici    schedule 01.10.2015
comment
@rici вы можете сказать, что это для обучения, поэтому я делаю это   -  person    schedule 01.10.2015
comment
Вы должны следить за _ в комментариях. Всегда используйте обратные кавычки, чтобы цитировать их, в противном случае они используются как курсив. Так что ваш предыдущий комментарий не читается. Но если вы говорите, что p__k правильно, то вам нужно быть более точным, потому что за первым _ не следует буква.   -  person rici    schedule 01.10.2015
comment
Зачем ? За символом подчеркивания p_ следует буква p   -  person    schedule 01.10.2015
comment
В p_ за буквой следует символ подчеркивания, а не наоборот. В p_9 за буквой p также следует символ подчеркивания, а в _uy_ последнее подчеркивание также стоит рядом с буквой y. Точность важна.   -  person rici    schedule 01.10.2015
comment
@rici хороший точный ответ на ваш вопрос: сделать так, чтобы за ним шла любая буква слева или справа, но другая сторона может быть любой другой   -  person    schedule 06.10.2015
comment
Так что же не так с p_9, t_5 и _uy_? Во всех этих случаях подчеркивание имеет букву либо слева, либо справа.   -  person rici    schedule 06.10.2015
comment
извините, это опечатка, правильно может быть _uy9, p_9,p_p9 неправильно _uy_, p__9,y_9u,y_y,7_y,__   -  person    schedule 07.10.2015
comment
А проблема с y_9u? y_y? 7_y? Во всех трех подчеркивание находится рядом с y.   -  person rici    schedule 08.10.2015
comment
упс y_9u верно, но y_y не содержит цифры, 7_y содержит цифру, но первый символ не может быть цифрой   -  person    schedule 13.10.2015

Ответы (1)


arrow_upward
2
arrow_downward

Вы указали следующие ограничения:

  • может содержать буквы, цифры и символы подчеркивания.
  • должен содержать хотя бы одну цифру
  • должен содержать хотя бы одно подчеркивание
  • не должен заканчиваться символом подчеркивания
  • не должен начинаться с цифры

Ограничения типа «по крайней мере одно X» соответствуют состояниям в конечном автомате. Поскольку у нас есть два таких ограничения, есть 2*2=4 состояния, которые управляют тем, нужна ли нам по-прежнему цифра или символ подчеркивания. Я буду сокращать состояния:

  • DU — нужна цифра, нужно подчеркивание
  • Du — нужна цифра, есть подчеркивание
  • dU — содержит цифру, необходимо подчеркивание
  • du — есть цифра, есть подчеркивание

Теперь мы можем создать таблицу переходов состояний:

STATE TRANSITIONS
      _  0-9 a-zA-Z
----- -- --- ------
 DU   Du dU  DU
 Du   Du du  Du
 dU   du dU  dU
 du   du du  du

где DU — начальное состояние. У вас есть дополнительные специальные требования для первого и последнего перехода состояния. Кроме того, конечное состояние может быть достигнуто только из состояния du. На самом деле, du само по себе могло бы быть конечным состоянием, если бы оно не было достигнуто через ввод _. Вместе с этими другими требованиями мы получаем следующую таблицу переходов состояний. Начальное состояние — S, а конечные состояния отмечены *. Я исключил незаконные переходы.

STATE TRANSITIONS
       _  0-9 a-zA-Z
----- --- --- -----
 S    Du   -   DU
 DU   Du  dU   DU
 Du   Du  du   Du
 dU   du' dU   dU
*du   du' du   du
 du'  du' du   du

Состояние du' — это состояние «мы увидели все, что нам нужно, но последним символом было подчеркивание, поэтому мы не можем здесь закончить». Эта таблица состояний не требует, чтобы после символа подчеркивания шла буква, но вы должны иметь возможность добавить это самостоятельно, используя аналогичный подход. Таблица состояний соответствует DFA, но я сомневаюсь, что вы сможете упростить ее, используя NFA.

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

([_][_a-zA-Z]*[0-9]|[a-zA-Z][a-zA-Z]*([_][_a-zA-Z]*[0-9]|[0-9][0-9a-zA-Z]*[_]+[0-9a-zA-Z]))[0-9a-zA-Z]*([_]+[0-9a-zA-Z]+)*

Ну, если только я не ошибся. Что на данном этапе вполне вероятно.

Для такого рода проверки неудобно использовать регулярные выражения. Вместо этого используйте более простой шаблон, например [_a-zA-Z][_0-9a-zA-Z]+, а затем проверьте, содержит ли совпавшая строка цифру и символ подчеркивания, а также соответствует ли она другим правилам, касающимся символов подчеркивания. Это хорошо работает, если идентификаторы каким-то образом разделены на языке ввода, например. пробелами или другими неидентифицирующими символами.

person amon    schedule 01.10.2015
comment
вы переворачиваете весь процесс, чтобы выполнить эту простую задачу, почему? я ценю ваш ответ, но просто любопытно - person ; 01.10.2015
comment
@Zulqurnainjutt То, что регулярные выражения и автоматы эквивалентны, не означает, что я всегда предпочитаю использовать регулярные выражения. Посмотрите на финальное регулярное выражение: оно длинное и сложное, и я бы никогда не разобрался с ним «просто так». Однако проблема имеет очень краткое и простое описание, если мы формулируем ее в терминах состояний и переходов между состояниями. Я обнаружил, что с машиной состояний намного проще работать. (Помогло и то, что я недавно прошел курс по формальным языкам и конечным автоматам, где нам приходилось решать похожие задачи.) - person amon; 01.10.2015
comment
Ваш ответ работает с идентификатором «d_3__abc2e», почему это так? потому что после 2-го подчеркивания есть оператор «_» справа и «цифра» слева, где буква? тогда он не должен его принимать. - person ; 06.10.2015