КАТЕГОРИИ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) П Архитектура- (3434) Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Война- (14632) Високи технологии- (1363) География- (913) Геология- (1438) 1065) House- (47672) Журналистика и масови медии- (912) Изобретения- (14524) Чужди езици- (4268) Компютри- (17799) Изкуство- (1338) История- (13644) Компютри- (11121 ) Художествена литература (373) Култура- (8427) Лингвистика- (374 ) Медицина- (12668 ) Naukovedenie- (506) Образование- (11852) Защита на труда- ( 3308) Педагогика- (5571) P Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Олимпиада- (1312) Политика- (7869) Право- (5454) Инструменти- ( 1369) Програмиране- (2801) Производство- (97182) Промишленост- (8706) Психология- (18388) Земеделие- (299) Социология- (6455) Спорт- (42831) Строителство- (4793) Търговия- (5050) Транспорт- (2929) Туризъм- (1568) Физика- (3942) ) Химия- (22929 ) Екология- (12095) Икономика- (9961) Електроника- (8441) Електротехника- (4623) Енергетика- (12629 )

Езикови операции




Вижте също:
  1. II. Еквивалентни формули, изразяващи някои логически операции чрез други.
  2. Активни операции
  3. Активни операции на търговски банки.
  4. Аритметични операции в октална нотация
  5. В Египет са били отглеждани пчели, са извършени хирургически операции, са били изгорени стъкла, е писано папирус и са направени много неща, които по-късно са били полезни за обществото по целия свят.
  6. В операцията Никопол-Кривой рог
  7. Валутни операции в Русия
  8. Валутни операции на търговските банки
  9. Валутни операции на кредитни институции.
  10. ВЪЗНИКВАНЕТО НА ПОТРЕБИТЕЛСКОТО СЪТРУДНИЧЕСТВО В ЧУЖДЕСТРАННИ СТРАНИ
  11. Въпрос 36. Валутни сделки на търговските банки.
  12. Изберете режим на рязане за работа 010 Вертикално сондиране

Независимо от факта, че формалните езици са множество от вериги от формата L (G) = {a | aÎ V *}, използването на зададени теоретични операции е ограничено. Така че за класа на езиците COP можете да използвате операцията на съюза, но е неприемливо да използвате операцията на пресичане и допълнения. Ако езикът е даден L (G) = {a | aÎ V *}, тогава комплектът на езика L (G) е множеството от вериги, които не принадлежат към V *. Те могат да бъдат всякакви вериги от всякакви символи. Ето защо този набор не е дефиниран. Ако са дадени два езика L 1 и L 2 , тогава операцията за тяхното пресичане може да бъде написана като: (L 1 Ç L 2 ) = ù (L L 1 Æ L 2 ). Но комплектът от веригите езици L1 и L2 не е дефиниран. Следователно е невъзможно да се осъществи функционирането на пресечната точка на двата езика L 1 и L 2 . Ето защо се казва, че класа на KS-езици е затворен за операцията на обединението и не е затворен за операциите на пресичане и добавяне. Бяха подчертани допълнителни операции по мултиплициране, разделяне, заместване, итерация, които разшириха възможностите за формиране на нови вериги и нови езици.

Умножение . Ако са дадени струните a 1 , a 2 Î V * на един език L (G) Í V *, тогава двойното умножение се свързва с всяка двойка вериги a 1 и a 2 нова верига a 1 a 2, получена чрез приписване на веригата вериги 1 а 2 .

Мултиплициращата операция често се нарича контакация или свързване.

Всеки низ от който и да е език може да се разглежда като конкатенация на неговите подрези и по-специално като конкатенация на символите, които го съставят.

Можете да говорите и за свързването на езици L 1 и L 2 . В същото време се формира нов език:

L = L 1 L 2 = {а 1 а 2 | a 1 Î L 1 ÍV 1 *, a 2 ÎL 2 ÍV 2 *}. V 1 * V 2 *. (28)

Ако L 1 = L 2 = L, тогава операцията на конкатенацията може да бъде написана като нормална мултипликативна операция, т.е.

LL = L2, LLL = L3 и т.н. (29)

За празна верига e, връзката

ea = ae = a, за всяко a ¼ V *. (30)

Реакцията на свързване е асоциативна, т.е.

(a 1 a 2 ) a 3 = a 1 (a 2 a 3 ) = a 1 a 2 a 3 . (31)

Може да се отбележи, че алгебра с една асоциативна двоична операция - умножение се нарича semigroup.

Дейност на дивизията Нека a = g 1 g 2 ÎL 1 ÍV 1 * и a 2 = g 2 ÎL 2 ÍV 2 *,

Ако за веригите от два езика L 1 и L 2 има идентични "опашки", тогава в резултат на извършването на операцията на разделяне ще се разграничат вериги, които са "глави" за веригите на езика L1, т.е.

L = L 1 / L 2 = {g 1 | g 1 g 2 ÎL 1 ÍV 1 *, g 2 ÎL 2 ÍV 2 *}. (32)

Нека 2 = g 2 g 1 ÎL 1 ÍV 1 * и a 2 = g 2 ÎL 2 ÍV 2 *,

Ако за веригите на два езика L 1 и L 2 има идентични "глави", тогава в резултат на извършването на операцията по разделяне ще се различават веригите, които са "опашките" за веригите на езика L1, т.е.



L = L 1 / L 2 = {g 1 | g 2 g 1 ÎL 1 VV 1 *, g 2 ÎL 2 ÍV 2 *}. (33)

Операция за замяна. Нека L е граматика

G = áVT; VN; J; Pn и езика L 1 с граматиката G 1 = áV T1 ; V N1 ; J 1 ; P 1 -. Сред набор от терминални символи на езика L се избира символът "а", който определя възможността за преход към езика L1, т.е. "a" ÎV T и ("a" ®L 1 ) .След това, когато символът "a" се появи във веригата aÎ L, е възможно да се извърши замяната на веригата a Î Î 1 . Ето как се формира нов език:

L * = L ("a" ® 1 ). (34)

Ако е даден набор от езици L 1 , L 2 , ... L n и езика L, в който са избрани символите "a 1 ", "a 2 ", ... "a n " измежду множеството терминални символи, тогава за string a ÎLÍV * съдържащ символа "a i ", можете да отидете на езика L i, като замените символа "a i " с низ a i ÎL i ÍV i *. По този начин се формира език L * = L ("a i " ®L i ). Обобщението на тази операция в множество езици е замяната на няколко езика на езика L, в който вместо всяко появяване на символа "a" се замества определена верига на съответния език, т.е.

L * = ("a 1 " ® L 1 , "a 2 " ® L 2 , ... "a n " ® L n ). (35)

Операциите на езиците L i и L, където i = 1, 2, ... n, генерират веригите на новия език a * Î L * като заменят символите "a i " на езика L с веригите на съответния език а i Î L i и заместването им веригите aÎ L Í V * се наричат ​​също така суперпозиции и операторът на суперпозицията е написан така:

S (L; " 1 "; "a 2 "; ... "a 2 " | L 1 , L 2 , ... L n ). (36)

Основното предимство на заместващата операция е, че тя има същия характер като правилата на COP граматиката. Следователно заместването на веригите на KS-език в друг KS-език може да се представи като заместване на KS-граматиката в друга KS-граматика, която отново дава KS-граматика. От това следва, че класа на KS-езици е затворен по отношение на заместващи и конкатенационни операции.

Итерация на операцията Съюзът на множеството езици L i , всеки от които е генериран от езика L чрез умножение, се нарича итерация на езика, т.е.

L * = L 0 È L 1 È L 2 è ... È L n = i = 0 è n V i , където L 0 = {e}. (37)

Ако i = 1,2, ... n, тогава итерация се нарича скъсена, т.е.

L * = L1 È L2 È ... È Ln = i = 1 n V i (38)

заключение

Учетените класове на официалните езици, правилата за образуване на вериги от знаци, алгоритми за синтактични структури за синтактичен анализ позволяват автоматизиране на синтактичния анализ на текстове. Тези идеи се използват широко в разработването на софтуер и хардуер на съвременните компютри.

Програма или хардуер, който преобразува програмен източник, написан на език на високо ниво, в модулите на обекта на езика на компютъра се нарича преводач. За да се организира такава трансформация, е необходимо да се познават азбуките на езиците и компютрите на високо ниво, правилата за конструиране на синтактични конструкции на текстове, написани на езика на високо ниво, и обектните модули на компютърен език. Това знание е вградено в синтаксиса на съответния език. По правило, за езика на високо ниво това е граматика за KS, за компютърна език тя е система от команди. Ако текстът на изходната програма е написан синтактично правилно, следващата стъпка е семантичен анализ на текста, подготовка и генериране на компютърната командна система. Тези произведения се определят от вида на компютъра и неговия език.


Тествайте въпроси и задачи

1. Дайте формално определение на езика, който да формира:

а) множества от положителни числа;

б) набор от думи на руския език;

в) набор от идентификатори на език за програмиране.

2. Нека VT = {0; 1; 2} и също a = 01, b = 2, g = 011. Напишете следните вериги: ab, ba, abg, a, 3. Опишете техните дължини, глави и опашки.

3. Нека граматиката G = á VT; VN; P; J - къде

VT = {a, b, c}, V N = {A, B, J}, J ¼ V N , P = {p1 = p = {p1 =;

p2 = b :: = a;

p3 = b :: = b;

p4 = A :: = c}.

Докажете истината или фалшивостта на изхода на следните вериги:

а) J => ... => a; b) J => ... => ac;

в) В => ... => Ac; d) aJ => ... => aab;

д) aBb => ... => acb.

Какъв тип граматика?

4. Опишете граматиката, чийто език се състои от набор от четни числа.

5. Опишете граматиката, чийто език се състои от странна последователност на знака "а".

6. Нека граматиката G = á VT; VN; P; J - къде

VT = {a}, VN = {A, J}, JVVN, P = {p1 = J = = a;

p2 = J :: = aJa}.

Вериги от какъв език генерира граматиката?

7. Нека граматиката G = á VT; VN; P; J - къде

VT = {a, b}, VN = {A, B, J}, JVVN, P = {p1 = J = B;

p2 = J = AJ;

p3 = AJ :: = a;

p4 = b :: = b}.

Вериги от какъв език генерира граматиката?

8. Нека граматиката G = á VT; VN; P; J - къде

VT = {a, b}, VN = {А, В, J}, JVVN, Р = {р1 = J :: = aA;

р2 = А :: = а;

p3 = А :: = В;

p4 = b :: = b b

p5 = b :: = b}.

Вериги от какъв език генерира граматиката?

9. Като се има предвид набор от правила P = {p1 = J :: = ABA;

р2 = А :: = Са;

p3 = A :: = bA;

p4 = C :: = d}.

Намерете матрици за връзки, таблици за търсене, синтаксиси и техните двоични еквиваленти за низ, започващ с буквата "d".

10. Като се има предвид набор от правила P = {p1 = J :: = ABA;

p2 = J = DE;

p3 = A :: = Ca;

p4 = В :: = bC;

p5 = С = = с;

р6 = D :: Е;

p7 = Е :: = cJC}.

Намерете матрици за връзки, таблици за търсене, синтаксисни дървета и техните двоични еквиваленти за низ, започващ с буквата "c".

11. Начертайте синтаксисните диаграми на програмния език на Pascal за синтактичните променливи:

<identifier>, <program>, <integer_less_>, <term>, <simple_expression>, <block_ end>, <hlavička_programu>.

12. Използвайки граматиката на аритметичните изрази (пример 14), създайте дървовидна структура и нейния двоичен еквивалент за изрази:

а) брадва (a + b) / c;

б) (а + Ь) / с;

c) (a + b) x (a-c) / (b-c).


Индивидуална задача

Като се има предвид граматиката G = á V T ; VN; P; J - къде

V T = { a , b , c } È {(,), +, -, x, /},

V N = {arifme_expression: -J>, <термин: - T>,

<multiplier: -M>, <операнд: -К>, <добавяне на операция: - S1>, <умножение: -S2>, <алтернативен символ: -S3>

J е първоначалният граматичен символ,

P = {p1 = J :: = T | JS1T; р2 = Т :: = М | TS2M;

p3 = M :: = K | S31JS32; p4 = S1 :: = "+" | "-";

p5 = S2 :: = "x" "/"; p6 = K :: = "a" | "б" | "C";

p71 = S31 :: = "("; p72 = S32 :: = ")"}.

Начертайте по опции за задачи:

1) синтаксисни диаграми за подмножество от правила

{pi; pj; pk};

2) синтактично дърво за аритметична експресия;

3) двоично дърво за аритметично изразяване.

Извършете граматически анализ на аритметичния израз за опции 1 - 30 за алгоритъма "отгоре-надолу" за опции 31 - 60 за алгоритъма "отдолу-нагоре".

номер на опцията индекси i, j, k аритметично изразяване номер на опцията индекси i, j, k
1,2,3 ((a + b) xc) + (a-b) / c 2,5,6
1,2,4 ((a + b) / c) - (a-b) / b 2,5,71
1,2,5 ((a2-b2) xc-b) / c 2,5,72
1.2.6 (a 3 + b 2 ) / (с + b) 2,6,71
1,2,71 ((a + b) - c) / (b + c) 2,6,72
1,2,72 (a - b) / (с 2 + а) 3,4,5
1,3,4 (a + b) / (b 2 х (а-с)) 3,4,6
1,3,5 (a 2 + b 2 ) / (bxa-c) 3,4,71
1,3,6 (a + b 2 ) / (b 2 + c 2 ) 3,4,72
1,3,71 (a 2 + b 2 ) / (b 2 -c) 3,5,6
1,3,72 (a 2 + b 2 ) x (b-c) 3,5,71
1,4,5 (a 2 - bx (a - c)) xc 3,5,72
1,4,6 ((a 2 -c) xb) хс 2 ) 3,6,71
1,4,71 (a-c) x (b 2 + c) 3,6,72
1,4,72 a + b + c 2 - b 2 4,5,6
1,5,6 a 2 + b 2 + c - b 4,5,71
1,5,71 a 2 / (b 2 -a + c) 4,5,72
1,5,72 a / (b2-a2-c) 4,6,71
1,6,71 2 + а 2 -с) 4,6,72
1,6,72 (б + а2-с) 5,6,71
2,3,4 а / (Ь-с) + (а + с) 5,6,72
2,3,5 a 2 x b 2 + (a-c)) 6,5,4
2,3,6 a 2 - b 2 - c 2 6,5,3
2,3,71 (a 2- b) / (b 2 -c) 6,5,2
2,3,72 ax (((a + b) / b + c) - а) 6,5,1
2,4,5 a / (((а-с) хб-а) + Ь) 5,4,3
2,4,6 а + ((ас (Ь + с) - а) - Ь) 5,4,2
2,4,71 а - (а - (bxc + c) + b) 5,4,1
2,4,72 а - (бис ((б-с) / а-с)) 4,3,2
2,5,71 а / (сек ((b + c) 2- а)) 4,3,1