Լեքսիկական (նիշային) վերլուծություն

Լեքսիկական կամ նիշային վերլուծությունը տեքստի մշակման այն փուլն է, երբ, ըստ նախապես տրված կանոնների, տեստը տրոհվում է առանձին հատվածների և ամեն մի հատվածի վերագրվում է իր տիպին համապատասխան պիտակ։ Օրինակ, թող որ տրված են ինչ-որ ծրագրավորման լեզվի ծրագրերի լեքսիկական վերլուծության հետևյալ մի քանի (ոչ լրիվ) կանոնները․

1. if, then, else, print բառերը ծառայողական բառեր են՝ ամեն մեկն իր անունով,

2. Տառով սկսվող և տառերից ու թվերից բաղկացած սիմվոլների անընդհատ հաջորդականությունը իդենտիֆիկատոր է,

3. Թվանշանների անընդհատ հաջորդականությունը ամբողջ թիվ է,

4. Երկու չակերտներով պարփակված և չակերտ չպարունակող տեքստի հատվածը տող է,

5. >, >=, <, <= և այլն, համեմատման գործողություններ են՝ ամեն մեկն իր անունով։

Եվ պետք է ըստ այս կանոնների լեքսիկական վերլուծության ենթարկել հետևյալ տեքստը․

if num >= 10 then
    print "Test done"

Սիմվոլների առաջին անընդհատ հատվածը if բառն է, որը, ըստ տրված կանոնների, ծառայողական բառ է։ Հաջորդ հատվածը num բառն է, որը չկա ծառայողական բառերի ցուցակում և, ըստ երկրորդ կանոնի, պետք է համարել իդենտիֆիկատոր։ >= սիմվոլների հաջորդականությունը մեծ է կամ հավասար համեմատման գործողությունն է, ըստ հինգերորդ կանոնի։ Ըստ երրորդ կանոնի 10 հաջորդականութթյունը ամբողջ թիվ է։ then և print բառերը նորից ծառայողական բառեր են։ Իսկ Test done հատվածը, ընդ որում՝ առանց ընդգրկող չակերտների, տող է։

Ընդունված տերմինաբանությամբ նախապես տրված տեքստից առանձնացված հատվածները կոչվում են լեքսեմներ (lexeme), իսկ նրանց համապատասխանեցված պիտակները՝ տոկեններ (token) կամ թոքեններ։ Եթե բերված օրինակի համար կազմենք լեքսեմների ու թոքեների աղյուսակը, ապա այն կունենա այսպիսի տեսք․

Լեքսեմ	Թոքեն
if	IF
num	IDENTIFIER
>=	GE
10	INTEGER
then	THEN
print	PRINT
Test done	STRING

Լեքսիկական վերլուծության ժամանակ նիշ առ նիշ անցում է կատարվում վերլուծության ենթական տեքստով և փորձ է կատարվում ճանաչել վերլուծության կանոններին համապատասխանող նիշերի ամենաերկար հաջորդականությունը։ Կարելի է լեքսիկական անալիզատորը ներկայացնել որպես վերջավոր ավտոմատ, և հմնականում հենց այդպես էլ արվում է։ Ավտոմատի սկզբնակական վիճակից, կողմնորոշվելով հերթական սիմվոլով, ընտրվում է վերլուծության համապատասխան կանոնը։ Այնուհետև ավտոմատն աշխատում և փոխում է իր վիճակներն այնքան ժամանակ, քանի դեռ չի հասել վերջնական վիճակի կամ քանի դեռ չի ավարտվել վերլուծության ենթարկվող տողը։ Առաջին դեպքում համարվում է, որ թոքենը ճանաչվել է, և ավտոմատը վերադառնում է սկզբնական վիճակին՝ նոր թոքեն ճանաչելու փորձ կատարելու համար։ Երկրորդ դեպքում, երբ ավարտվել է տողի ընթերցումը, բայց ավտոմատը չի հասել որևէ վերջնական վիճակի, կա՛մ կարելի է տալ սխալի մասին ազդանշան, կա՛մ պահանջել ևս մի տող՝ վերլուծությունը շարունակելու համար։

Ստորև բերված է մի դետերմինացված վերջավոր ավտոմատի (DFA) ուրվապատկեր, որը «կարողանում է ճանաչել» իդենտիֆիկատորները, չակերտների մեջ վերցրած տողերը և ամբողջ թվերը։

Հերթական սիմվոլը կարդալուց հետո «1» համարով վիճակում որոշում է կայացվում, թե որ ուղղությամբ պետք է շարժվել, իսկ «3», «4» և «5» վիճակները ցույց են տալիս, թե ինչ տիպի տեքստ է ճանաչվել։

Լեքսիկական վերլուծության ժամանակ հոսքից տվյալների ընթերցումը կատարվում է նիշ առ նիշ։ Այդ նիշերն իրար կցելու և ամբողջական տող ստանալու համար է սահմանված char-list-to-string ֆունկցիան․

(defun char-list-to-string (chars)
  (apply #'concatenate 'string (mapcar #'string chars)))

Ամենատարածված դեպքերն են, երբ երբ հոսքից պետք է կարդալ կա՛մ որևէ տիպի նիշերի շարք, կա՛մ տրված երկու նիշերի միջև պարփակված տեքստ։ Օրինակ, եթե հոսքի ընթացիկ նիշը տառ է՝ alpha-char-p, ապա պետք կարդալ նրան հաջորդող բոլոր տառերն ու թվանշանները՝ alphanumericp, ապա պարզել կարդացածը իդենտիֆիկատո՞ր է, թե՞ ծառայողական բառ։ Տրված պրեդիկատին բավարարող նիշերի շղթա կարդալու համար սահմանված է scan-sequence ֆունկցիան։

(defun scan-sequence (fu sm)
  (char-list-to-string
    (loop for ch = (read-char sm nil)
          until (null ch)
          while (funcall fu ch)
          collect ch
          finally (when ch (unread-char ch sm)))))

Իսկ տրված երկու նիշերի մեջ պարփակված նիշերի շարքը կարդալու համար սահմանված է scan-quoted ֆունկցիան։

(defun scan-quoted (co ci sm)
  (if (char= co (read-char sm nil))
    (prog1 
      (scan-sequence #'(lambda (c) (char/= c ci)) sm)
      (read-char sm nil))))

Հիմանականում անհրաժեշտ է լինում ընթերցման հոսքից հեռացնել իմաստ չպարունակող բացատանիշերը (white spaces)։ Որպեսզի հնարավոր լինի scan-sequence ֆունկցիայով կարդալ իրարա հաջորդող բացատանիշերը, սահմանված են space-char-p պրեդիկատը և skip-white-spaces ֆունկցիան։

(defun space-char-p (c)
  (or (char= c #\Newline)
      (char= c #\Tab)
      (char= c #\Space)
      (char= c #\Return)))
(defun skip-white-spaces (stream)
  (scan-sequence #'space-char-p stream))

Իդենտիֆիկատորներն ու ծառայողական բառերը կարդացվոլու են նույն կանոնով։ +keywords+ ցուցակում առանձնացված են այն լեքսեմները, որոք ծառայողական բառեր են, և նրանցից ամեն մեկին համապատասխանեցված է իր թոքենը։

(defconstant +keywords+
  '(("if"    . :lex-if)
    ("then"  . :lex-then)
    ("else"  . :lex-then)
    ("for"   . :lex-for)
    ("while" . :lex-while)
    ("input" . :lex-input)
    ("print" . :lex-print)))

oper-char-p պրեդիկատը դրական պատասխան է տալիս իր արգումենտում տրված այն նիշերի համար, որոնցով կարելի է կազմել հարաբերության կամ թվաբանական գործողություններ։

(defun oper-char-p (c)
  (member c '(#\= #\> #\< #\+ #\- #\* #\/ #\%)))

Իսկ +operations+ ցուցակում հավաքված են այն գործողությունների նշանները, որոնք կազմված են open-char-p պրեդիկատին բավարարող նիշերից (կամ դրանց համակցությունից)։

(defconstant +operations+
  '(("="  . :lex-equal)
    ("<>" . :lex-not-equal)
    (">"  . :lex-greater)
    (">=" . :lex-great-equal)
    ("<"  . :lex-lesser)
    ("<=" . :lex-less-equal)
    ("+"  . :lex-add)
    ("-"  . :lex-sub)
    ("*"  . :lex-mul)
    ("/"  . :lex-div)
    ("%"  . :lex-mod)))

Պարզելու համար, թե արդյոք կարդացած լեքսեմը պատկանո՞ւմ է +keywords+ կամ +operations+ ցուցակներից որևէ մեկին, սահմանված է known-lexeme ֆունկցիան։

(defun known-lexeme (lexeme pairs &optional (default :lex-unknown))
  (let ((res (find lexeme pairs :test #'equal :key #'first)))
    (if res res (cons lexeme default))))

Եվ վերջապես, լեքսիկական (նիշային) վերլուծություն կատարող scan-lexeme հիմնական ֆունկցիան։ Այն նախապես ընթերցման հոսքից հեռացնում է բացատանիշերը։ Ապա, ըստ դեն նետված բացատանիշերին հաջորդող առաջին նիշի, որոշում է կայացնում, թե ինչ լեքսեմ պետք է կարդալ։

(defun scan-lexeme (stream)
  (skip-white-spaces stream)
  (let ((ch (peek-char nil stream nil)))
    (cond
      ((null ch)
       (cons "<EOS>" :lex-eos))
      ((alpha-char-p ch)
       (known-lexeme (scan-sequence #'alphanumericp stream)
             +keywords+ :lex-identifier))
      ((digit-char-p ch)
       (cons (scan-sequence #'digit-char-p stream)
         :lex-integer))
      ((oper-char-p ch)
       (known-lexeme (scan-sequence #'oper-char-p stream)
             +operations+))
      ((char= #\" ch)
       (cons (scan-quoted #\" #\" stream)
         :lex-string))
      (t (cons (read-char stream nil) :lex-character)))))

Վերջ։ Հիմա պատրաստենք մի ֆայլ, որ պարունակում է տեստային տվյալներ։ Անվանենք ֆայլը test0.txt և նրանում գրառենք հետևյալը․

" asda asdkak "
1234
abcd3434jf
if
then
=
>
<>
%
$
#

Այնուհետև Common Lisp միջավայրում, հաշվարկենք հետևյալ կոդը․

(with-open-file (inp "test0.txt" :direction :input)
  (loop for lex = (scan-lexeme inp)
        until (eq (cdr lex) :lex-eos)
        do (print lex)))
(terpri)

Կատարման արդյունքում պետք է արտաշվի հետևյալը․

(" asda asdkak " . :LEX-STRING) 
("1234" . :LEX-INTEGER) 
("abcd3434jf" . :LEX-IDENTIFIER) 
("if" . :LEX-IF) 
("then" . :LEX-THEN) 
("=" . :LEX-EQUAL) 
(">" . :LEX-GREATER) 
("<>" . :LEX-NOT-EQUAL) 
("%" . :LEX-MOD) 
(#\$ . :LEX-CHARACTER) 
(#\# . :LEX-CHARACTER) 

Որն էլ ցույց է տալիս, որ կառուցված լեքսիկական (նիշային) վերլուծությունը ճիշտ է աշխատում։