Резумируем основные положения, изложенные ранее для реализации конкретного транслятора.

Алфавит — это некоторое конечное множество I с элементами, которые называются символами. Цепочкой или словом  в алфавите I является конечная последовательность символов его символов. Цепочка, которая не содержит ни одного символа (обозначается ε), называется пустой. Языком в алфавите I является произвольное множество цепочек  в I. Над языками возможны операции, которые порождают новые языки. Катенация цепочек Х и Y есть цепочка XY. Если L₁ и L₂ — два языка в алфавите I, то их теоретико-множественное объединение L₁L₂= {x|x`in` L₁ или x`in` L₂} и катенация L₁ • L₂={xy| x `in` L₁& y`in` L₂} являются новыми языками. Если L- язык, то итерация- возведение в степень L*=L₀UL₁UL₂...=S_i=0Lⁱ, где L₀ ={ ε }, Lⁱ = L L ^i-1, i>1 есть новый язык.

Допустим, что символы (,),*,| не принадлежат алфавиту I. Тогда определенные цепочки в алфавите IU{(,),*,|} называются регулярными выражениями в I.

Каждое регулярное выражение однозначно определяет язык, который называется регулярным языком в алфавите I.

Регулярные выражения и задаваемые ими регулярные языки определяются так. Если а принадлежит I, то цепочка из одного символа а есть регулярное выражение, которое определяет язык, состоящий из одной цепочки а. Если цепочки r₁, r₂..., r_n является регулярными выражениями для определения регулярных языков R₁,R₂, ...,R_n,то цепочки r₁ |r₂ |.., |r_n , (r₁ ), r₁*  также есть регулярные выражения, представляющие соответственно регулярные языки R_1`uu` R_2`uu` ...,`uu` R_n, R₁,R₂, ...,R_n ,R₁ ^*.

Приведем примеры регулярных выражений над алфавитом I = {0, 1}.

Цепочка 01 представляет язык из одной цепочки {0 1};

Цепочка 1| 1(0|1)*1 задает язык, содержащий все цепочки, начинающиеся и оканчивающиеся 1.

Более сложные языки (множества) конструктивно задаются с помощью грамматик. Грамматика G = (Т, N, Р, S) состоит из объектов: Т - алфавит терминальных символов; N — алфавит нетерминальных символов (N `nn` Т = {}); S `in` N — исходный нетерминал; Р — конечное множество  правил вывода вида А -> w, где А `in` N и w есть цепочка в алфавите N U Т.

Цепочка `eta` непосредственно выводима из цепочки `sigma` в грамматике  G   обозначается `sigma` ->`eta` ) тогда и только тогда, когда существуют цепочки `alpha` ,`beta` ,`nu` и нетерминал А, такие, что `sigma` = `alpha` A`beta` , `eta` = `alpha` `nu` `beta` и А -> `nu` `in` Р.

Цепочка `alpha` _n выводима из цепочки `alpha` ₀, (обозначение `alpha` ₀ =*>`alpha` _n) либо при `alpha` ₀ =`alpha` _n либо, если существуют последовательность цепочек `alpha` ₁,`alpha` ₂,...`alpha` _n таких, что  `alpha` _{i-1=>`alpha` i}для i = 1,...n.

Язык L(G), определяемый грамматикой G, представляет множество  терминальных цепочек w в алфавите Т, выводимых из начального не-терминала S с помощью правил Р, т. е.

L (G) = {w| S=>w, w — терминальная цепочка}.

Приведем примеры грамматик и задаваемых ими языков.

Грамматика G₁ = (Т₁,  N₁, Р₁, S) ,где Т₁ = {х, у, z, w}, N₁ = {S, А, В}, Р₁= {S-> АВ, В-> х, В-> у, А->z, А-> w}, определяет язык L (G₁) {zx, zy, wx, wy}.

Грамматика G₂ = (Т₂, N₂, Р₂, А), где Т₂ = {х, +, [,]}, N₂= {А, В}, Р₂ = {А -> х, А->  [В], В-> А, В -> В + А}, определяет язык L (G₂), состоящий из всех выражений, составленных из операндов х, операции + и квадратных скобок, вида х, [х], [х + х], [[х]], [х+ х+ х].

Грамматика G₃ = (Т₃, N₃, P₃E), где Т₃ = {d,n, +, —, /,*, [,]}, N₃= {Е}, Р₃= {E->d, Е->n, Е->[E], Е->[Е+ Е], Е->[Е — Е], Е->[Е* Е], Е-> [Е/Е]}, определяет язык L (G₃), состоящий из всех выражений в полной скобочной записи с операндами d и n и операциями +,-, *, /.

Имеются другие варианты грамматик, обладающие той же мощностью, но являющиеся во многих отношениях более наглядными. Это так называемые расширенные грамматики. Расширенная грамматика задается списком пар А_i-->r_i , где все Аi — различные нетерминальные символы алфавита N; r_i — регулярные выражения в алфавите N `uu` Т. Терминальный алфавит Т составляют символы, которые встречаются в цепочках r_i, кроме символов из NU{(,),*,|}. Нетерминал первой пары считается главным, а алфавит терминальных символов извлекается из правых частей пар.

Опишем примеры расширенных грамматик.

Грамматики G₁₁ = {S-> АВ, B`uu` х | у, A->z|w} или G₁₂ = {S->{(z|w)(x|y) } задают тот же язык, что и G₁.

Грамматика G₂₂ = {А->х|[В], В->A|В + А} или->

G₂₂= {А->х|[В], В->А {+А}*} или

G₂₃= {А->х|[А (+A)*] } задают тот же язык, что и G₂.

Грамматики G₃₁ = {Е->d|n|[Е]|Е [+|-|*|/] Е]} определяет тот же язык, что и G₃.