LINUX.ORG.RU

OCaml: первые шаги


0

0

Решил разобраться в хитросплетениях современных (полу)функциональных языков
Начал с OCaml. Пробная программа - простейший интерпретатор арифметических выражений,
представленных в виде текстовых строк. Соответсвенно в такой программе необходима функция
лексического анализа вида

lexicalAnalys: string -> token list ,

где тип token имеет приблизительно следующий вид

type tokens = (* Типы лексем *) 
		
		TnInt of int	| (* 12345 *)
		TnPlus		| (* + *)
		TnMinus		| (* - *)
		TnMul		| (* * *)
		TnDiv		| (* / *)
		TnOpenP		| (* ( *)
		TnCloseP	  (* ) *)
		
;;

Вопрос:

Как правильно в функциональном стиле и без существенной потери производительности реализовать
функцию lexicalAnalys ? Все мои идеи своядтся к активному использованию циклов, переменных 
состояния соответсвующего конечного автомата или к тормозному и некрасивому разрезанию 
анализируемых строк на части. Циклы и переменные - злостная императивщина, разрезание строк -
зело ресурсоемкая операция. А как идеологически правильно ? 

я не знаком с окамлом, но мне кажется, что все такие подобные задачи на ура решаются методом рекурсивного спуска. (если конечно грамматика его допускает)

anonymous
()

Добавлю, еще, что стоит посмотреть на Parsec (Parser Combinators) - библиотека для написания парсеров на чистом функциональном языке - Haskell.

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

Это понятно. Вопрос не в этом, вопрос в том, как правильно работать со
 строками в OCaml-е не прибегая к имепративным "шутчкам" или к тупому 
клонированию строк.

Вот, например, код на С выделющий во входной последовательности некое 
число


char * inputStrBuf; 
uint inputStrBufSize = strlen(inputStrBuf);

...

char intBuf [MAX_INT_LENGTH];
uint curBufIndex=0;

...
for (uint i=0; i<inputStrBufSize; i++) 
{
   ...

   if (isDigit(inputStrBuf[i])) 
    {
      do {                     

           intBuf[curBufIndex]=inputStrBuf[i];
    
      } while (++curBufIndex,isDigit(inputStrBuff[++i]))

      intBuf[curBufIndex]=0;

      value = atoi(intBuf);

      ...
    }

    ...
}

Впринице в меру изящно. Тоже самое или почти тоже самое можно написать
 на OCaml-е, используя циклы и императивные переменные (счетчики 
циклов) - будет выглядеть тоже довольно хорошо. 

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









 

ukez
() автор топика
Ответ на: комментарий от ukez

Догнала я. Вот так примерно надо ...

type token = (* лексемы входного языка *) 

	    TknConst of int | (* 123456 *) 
	    TknPlus         | (* + *)
	    TknMinus        | (* - *)
	    TknMul          | (* * *)
	    TknDiv          | (* / *)
	    TknOpenP        | (* ( *)	    
	    TknCloseP         (* ) *)	    	    
;;	    
	    
	    
let rec lexicalAnalys input_string index = (* Функция лексического анализа *)

	    if String.length input_string <= index 
		    then [] 
		    else match String.get input_string index with 
		    
			'0'..'9' -> let rec skipForNonDigit input_string index = (* пропускает цифровые символы *)

					if String.length input_string <= index 
					    
					    then index 
					    else     
					
					    match String.get input_string index with 
							'0'..'9' -> skipForNonDigit input_string (index+1)
							|  _     -> index
						
				    in
				    let skipTo = skipForNonDigit input_string index 
				    in 			
				    List.append [TknConst (int_of_string (String.sub input_string index (skipTo-index)))]  (lexicalAnalys input_string skipTo)    
				    
		      | '+'      -> List.append [TknPlus]  (lexicalAnalys input_string (index+1)) 
		      | '-'      -> List.append [TknMinus] (lexicalAnalys input_string (index+1)) 
		      | '*'      -> List.append [TknMul]   (lexicalAnalys input_string (index+1)) 	    
		      | '/'      -> List.append [TknDiv]   (lexicalAnalys input_string (index+1)) 	    
		      | '('      -> List.append [TknOpenP] (lexicalAnalys input_string (index+1)) 	    
		      | ')'      -> List.append [TknCloseP](lexicalAnalys input_string (index+1)) 	    
		      | ' '      -> lexicalAnalys input_string (index+1)	    
		      |  _       -> []	    
				    
;;	    	    




let rec printList lst = (* печатает список лексем *)
    let printToken tkn = 
		match tkn with 
		    
		    TknConst x -> print_string " Const "; print_int x	
		  | TknPlus    -> print_string " + "
		  | TknMinus   -> print_string " - "
		  | TknDiv     -> print_string " / "
		  | TknMul     -> print_string " * "
		  | TknOpenP   -> print_string " ( "
		  | TknCloseP  -> print_string " ) "
    in
    match lst with 
	 []     -> print_newline
       | hd::tl -> printToken hd; printList tl
;;       
       

let main() = printList ( lexicalAnalys (read_line()) 0);;

main();;



ukez
() автор топика
Ответ на: комментарий от svr69

Это штуки конечно полезные, но хотелось решить задачку "в лоб", без использования левых тулз, в целях обучения.

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