Как переходить между состояниями?

Question

[dearname]

Добрый вечер, не могу понять, как переходить между состояниями в лексическом анализаторе. Вот взял я один символ из файла, потом определяю, что он цифра, но возможно 3 случая тогда, к примеру,
a=3 - я должен вставить в вектор, индификатор "a"; да, но так как нету пробела, у меня "a=3" заносится в одну ячейку вектора.
c a= 3 - так же "a=" - в одной ячейке.
вот только это работает a = 3.
как мне вот запоминать, я ведь все время работаю, с одним символом.
Можно хотя бы с цифрами пояснить, то есть показать, как в данном случае будет переход состояний осуществляться. Мы должны с каждым новым символом находится в каком-то состоянии, это я понимаю, но вот как это в коде, хотя бы на таком маленьком примере, можете показать. Дальше я сам реализую.

Данный код, считывает файл, и заносит в вектор все слова этого файла. Предположим у меня в попалась вот такая вот конструкция a=3 - как мне разрешить эту ситуацию, чтобы в векторе было не "a=3", а "a", "=", "3" то есть 3 ячейки занимает в векторе эта строка.

#include "stdafx.h"
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <vector>

using namespace std;

struct Lexeme {	
	int start, end;
	string lexeme;
};
vector<Lexeme> v;
void gToken(ifstream &fin, vector<Lexeme> &v);
void wToken();
int main()
{
	char filename[30];
	ifstream fin;
	char q;
	//cin >> filename;
	fin.open("text.txt");
	gToken(fin, v);
	fin.close();
	wToken();
	system("PAUSE");
	return EXIT_SUCCESS;
}
void gToken(ifstream &fin, vector<Lexeme> &v)
{
	int j = 0;
	char ch;
	Lexeme l;
	while (fin >> ch) 
	{
		int i = 0;
		l.lexeme += ch;
		while (fin.get(ch))
		{	
		if (ch != ' ' && ch != '\n')
		{
			cout << ch<<endl;
					l.lexeme += ch;
			}
		else
		{
			j++;
			l.start = j - i;
			l.end=j;
			break;
		}
		}
	v.push_back(l);
	l.lexeme ="";
	}
}
void wToken()
{
	for (int i = 0; i < v.size(); i++) cout << v[i].lexeme << endl;
}

Answer 1

[Rsa97]

Вам нужно для начала расписать лексемы, построить конечный автомат и доработать его для вычисления значений лексем. Пример для алфавита [a-z0-9=], идентификаторов, целых чисел и присвоения:
<буква> := [a-z]
<цифра> := [0-9]
<равно> := [=]
<идентификатор> := <буква>(<буква>|<цифра>)*
<число> := <цифра>(<цифра>)*
Автомат:

_    [a-z]  [0-9]  [=]  ¬
s0    s1     s2    ok  end
s1    s1     s1    ok  ok
s2    ok     s2    ok  ok

Доработанный автомат:

_       in == ['a'-'z']                     in == ['0'-'9']                    in == ['=']           ¬
s0    val := in; next; s1                 val := in-'0'; next; s2            next; ret(ASSIGN)  ret(EOT)
s1    val := concat(val, in); next; s1    val := concat(val, in); next; s1   ret(IDENT, val)    ret(IDENT, val)
s2    ret(INTEGER, val)                   val := val*10+in-'0'; next; s2     ret(INTEGER, val)  ret(INTEGER, val)

s0 - исходное состояние, in - текущий символ, next - переход к следующему символу в потоке, ret возвращает тип лексемы и её значение.
Список переходов при анализе 'a1=95':
Первый вызов:

s0 ('a') -> val := 'a'; next; s1
s1 ('1') -> val := 'a1'; next; s1
s1 ('=') -> ret(IDENT, 'a1')

Второй вызов:
s0 ('=') -> next; ret(ASSIGN)
Третий вызов:

s0 ('9') -> val := 9; next; s2
s2 ('5') -> val := 95; next; s2
s2 (¬) -> ret(INTEGER, 95)

Следующие вызовы:
s0 (¬) -> ret(EOT)

Comments

[dearname]

Спасибо, но не могли бы вы показать как с++ переходы между состояниями происходят, мне вот сам алгоритм понятен. Пускай даже на каком то маленьком примере, я разберусь дальше, у меня именно это вызывает ступор.

[Rsa97]

Самый простой (но не самый эффективный) способ - через switch\case. Пример на псевдокоде:

string val_str;
int val_int;
int state = 0;
while (1) {
  switch(state) {
    case 0:
      if (*in >= 'a' && *in <= 'z') {
        val_str = *(in++);
        state = 1;
      } else if (*in >= '0' && *in <= '9') {
        val_int = *(in++)-'0';
        state = 2;
      } else if (*in == '=') {
        in++;
        return (ASSIGN, NULL);
      }
      else
        return (EOT, NULL);
      break;
    case 1:
      if ((*in >= 'a' && *in <= 'z') || (*in >= '0' && *in <= '9')
        val_str += *(in++);
      else
        return (IDENT, val_str);
      break;
    case 2:
      if (*in >= '0' && *in <= '9')
        val_int = val_int*10+(*(in++)-'0');
      else
        return (INTEGER, val_int);
      break;
  }
}

[dearname]

*(in++) - это следующий символ, который после *in?

[Rsa97]

Это эквивалентно следующей записи:

old_in = in;
in++;
val = *old_in;

[Rsa97]

В C++ оператор постинкремента X++ имеет результатом значение X до увеличения, преинкремент ++X - после увеличения. Аналогично постдекремент X-- и предекремент --X.

[dearname]

хорошо, спасибо, я думаю, в данном случае val_str += (char)*(in++); - так правильней

[Rsa97]

in скорее всего будет иметь тип char *, так что разницы нет.

[dearname]

а я ведь, могу заменить так, к примеру,
char c;
fin.get(c);
if (c >= 'a' && c <= 'z') {
fin++;
fin.get(c)
val_str = c;
state = 1;

т.е использовать fstream

[dearname]

точнее не могли бы вы написать, как вы в данной реализации подключали поток с файлом, то есть как обьявляли в том примере, который вы выше написали.

[Rsa97]

Если хотите работ ать с потоком, то надо объявлять переменную, содержащую текущий символ, поскольку .get() переходит к следующему символу, что не всегда нужно. Я работаю в старом добром C без плюсов, поэтому работаю через указатели с текстом, считанным в память.

[dearname]

а можете, показать, как тогда в си правильней обьявить именно этот поток?

[Rsa97]

Объявите глобальную или классовую, смотря как пишете программу, переменную currentСhar. При открытии потока сразу забирайте первый символ currentСhar = fin.get(). Вместо *in просто используйте эту переменную. Вместо in++ получайте следующий символ.

[dearname]

Я так реализовал, но он что-то вообще не едет в никакую. Зацикливается и выдает только "EOT | NULL

// lexeme3.cpp: определяет точку входа для консольного приложения.
//
#define _CRT_SECURE_NO_WARNINGS
#include "stdafx.h"
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <iostream>

using namespace std;
int v(FILE* in);
int _tmain(int argc, _TCHAR* argv[])
{

	FILE *in;
	in=fopen("text.txt", "r");

	v(in);
	
	return 0;
}


int v(FILE* in) {

	string val_str;
	int val_int;
	int state = 0;
	while (in) {
		switch (state) {
		case 0:
			if ((char)in >= 'a' && (char)in <= 'z') {
				val_str = (char)(in++);
				state = 1;
			}
			else if ((char)in >= '0' && (char)in <= '9') {
				val_int = (char)(in++) - '0';
				state = 2;
			}
			else if ((char)in == '=') {
				in++;
				cout << "ASSIGN | NULL" << endl;
				return 0;
			}
			else {
				cout << "EOT| NULL" << endl;
			}
			break;
		case 1:
			if (((char)in >= 'a' && (char)in <= 'z') || ((char)in >= '0' && (char)in <= '9'))
				val_str += (char)(in++);
			else {
				cout << "IDENT| "<<val_str << endl;
				return 0;
			}
			break;
		case 2:
			if ((char)in >= '0' && (char)in <= '9')
				val_int = val_int * 10 + ((char)(in++) - '0');
			else {
				cout << "INTEGER| " << val_int << endl;
				return 0;
			}
				
			break;
		}
	}
	return 0;

}

[Rsa97]

@dearname Вы не понимаете основных принципов работы с данными. Если fopen открывает файл, то возвращает указатель на дескриптор файла (в вашем случае in). *in - это не символ из файла, а собственно дескриптор. in++ и вас переходит не к следующему символу, а к следующему дескриптору.
Если хотите работать напрямую с файлом, то:

char currentChar;
FILE *in;

#define getNextChar fread(&currentChar, sizeof(char), 1, in)

void main(void) {
  in = fopen("text.txt", "r");
  getNextChar;
  while (getLexem());
}
int getLexem(void) {
  string val_str;
  int val_int;
  int state = 0;
  while (1)
    switch (state) {
      case 0:
        if (currentChar >= 'a' && currentChar <= 'z') {
          val_str = currentChar;
          getNextChar;
          state = 1;
        }
        . . .
    }
  }
}

Answer 2

[jcmvbkbc]

открой для себя flex