Блоґ одного кібера

Історія хвороби контуженого інформаційним вибухом

Лексичний аналіз в Python

leave a comment »

Як і обіцяв, пишу про те, як робляться лексичні аналізатори в Python.

Лексичні аналізатори пишуться досить просто через те, що кожен вид токенів зазвичай належить якійсь регулярній мові, і якщо ви знаєте регулярні вирази, то перетворення цього регулярного виразу в скінченний автомат що його розпізнає не становить жодних проблем. Я правда на жаль, не знаю як це робиться, мене вчили схеми Томпсона, але чомусь не зустрічав в інтернеті про неї ніяких згадок.

Загалом кожен лексичний аналізатор будується по схемі: шаблон -> що зробити, якщо на вхід потрапить послідовність символів яка цьому шаблону відповідає. Таку схему колись передавали Flex, який по ній писав код скінченного автомата на C. А в Python, як виявилось має для цього клас в модулі re, який чомусь не описується в документації (думаю це рано чи пізно виправлять).

Ну, і давайте зробимо лексичний аналізатор, який розфарбовує свій код різними кольорами. (Я хотів розказати на прикладі підсвічування вікірозмітки, але вона здається занадто складна, бо мені довелось вивчити про регулярні вирази вдвічі більше ніж я знав). Програму я вже написав, тепер тільки пройдусь по ній пояснюючи що й до чого.

Підключаємо модуль в якому є лексичний аналізатор

import re

Задаємо деякі кольори. Це працює для юніксівського терміналу, в консолі windows 7 чомусь не працює.

class Color():
	none = "\033[0m"
	red = "\033[31m"
	magenta = "\033[95m"
	yellow = "\033[33m"
	cyan = "\033[36m"
	blue = "\033[94m"
	green = "\033[92m"
	graybk = "\033[100m"
color=Color()

Далі йде набір функцій, які кажуть що робити з кожним видом токена. Кожна має два параметри – об’єкт лексичного аналізатора (поняття не маю навіщо він їй), і текст токена. Значення яке вона повертає буде передаватись на вихід аналізатора. В нас кожна функція просто повертає текст токена, причіпивши команду для зміни кольору тексту в терміналі:

def comment(sc,tok):
	return color.blue+tok

def identifier(sc,tok):
	return color.none+tok

def keyword(sc,tok):
	return color.yellow+tok

def operator(sc,tok):
	return color.red+tok

def spacing(sc,tok):
	return color.graybk+tok+color.none

def text(sc,tok):
	return color.magenta+tok

def number(sc,tok):
	return color.green+tok

Ну, і сама суть – конструктор сканера. В конструктор передаєтсья список пар (шаблон, функція яка викликається при збігу з цим шаблоном). Вони передаються саме як список, а не як словник, тому що тут досить важливий порядок пар. Наприклад якщо в вас бувають лексеми “=” та “==”, то вам треба передати шаблон “==” перед “=”, інакше аналізатор рядок “==” завжди буде розпізнавати як два окремі токени.

parser = re.Scanner([
	(r"[0-9]+",number),
	(r"#.*\n",comment),
	(r"r?'(.*[^\\])?'",text),
	(r'r?"(.*[^\\])?"',text),
	(r"(import|class|def|return|if|for|while|yield)",keyword),
	(r"[=+\-*/><\(\)\[\]:,.]=?",operator),
	(r"[a-zA-Z_][a-zA-Z0-9]*",identifier),
	(r"\s*",spacing),
])

Далі ми читаємо свій код, і передаємо його лексичному аналізатору. Лексичний аналізатор повертає дві змінні: список токенів, і все що залишилось. Те що залишилось – просто не підійшло жодному шаблону, і його наявність (ненульова довжина) означає синтаксичну помилку в тексті що аналізується, або помилку в проектуванні аналізатора.

text = open("autoscanner.py","r").read()

tokens,rest = parser.scan(text)

print "".join(tokens)
if len(rest)>0:
	print "REST:"+color.none,rest

Вивід на екран, кінець. Вчіть регулярні вирази!

P.S. Про лексичний аналіз української мови – читайте тут.

Advertisements

Written by bunyk

Листопад 30, 2010 at 11:54

Оприлюднено в Кодерство, Розмітка

Tagged with

Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: