Грамматика с фразовой структурой

Грамматика с фразовой структурой — формальная грамматика, алгебраическая структура, состоящая из упорядоченной четвёрки G=(N, T, P, S) и определённой на ней неявно операцией конкатенации.

  • N — конечное множество нетерминальных символов
  • T — не пересекающееся с N конечное множество терминальных символов
  • P — набор ограничивающих правил (продукций)
  • S — стартовый (начальный символ)

Пример Грамматикой, порождающей язык {0n1n | n≥0}, является G: G= ({S}, {0,1}, P, S), где P = {S→0S1, S→ε}.

Понятие выводимости: Если αβγ последовательный набор символов языка G, а β→δ правило этого языка, то αβγ=>αδγ (αδγ непосредственно выводима из αβγ в G).

Цепь — последовательное присваивание нетерминальных символов. Цикл — замкнутая цепь

x (x ∈ N) — недоступный символ, если x неэквивалентен стартовому символу S (x ≠ S) и не существует выводов типа S+→αxβ. Символ называется непродуктивным, если не существует строки γ, такой, что нетерминальный символ не будет присвоен γ (x→γ) Символ называется бесполезным, если он непродуктивен или недоступен.

Литература

  • Ахо, Дж. Ульман «Теория синтаксического анализа, перевода и компиляции», Т.1 «Синтаксический анализ», М.: Мир, 1978
  • Р. Хантер «Проектирование и конструирование компиляторов», ФиС, 1984

Ссылки

Read other articles:

Murad II

Murad IIمراد ثانىLukisan Murat II karya Konstantin KapıdağlıSultan Utsmaniyah Ke-6 periode pertamaBerkuasa26 Mei 1421 – Agustus 1444PendahuluMehmed IPenerusMehmed IIperiode keduaBerkuasaSeptember 1446 – 3 Februari 1451PendahuluMehmed IIPenerusMehmed IIInformasi pribadiKelahiranJuni 1404Amasya, Kesultanan UtsmaniyahKematian3 Februari 1451Edirne, Kesultanan UtsmaniyahPemakamanKomplek Muradiye, BursaWangsaUtsmaniyahAyahMehmed IIbuEmine HatunPasanganYeni HatunHatice Halime HatunHü...

 

Anaximenes

AnaximenesNama dalam bahasa asli(grc) Ἀναξιμένης BiografiKelahirank. 585 SM Miletos Kematiank. 525 SM (59/60 tahun)Miletos Data pribadiAgamaHylemorfisme KegiatanSpesialisasiFilsafat dan literary activity (en) PekerjaanFilsuf, astronom, penulis dan pengarang prosa PeriodeEra Klasik AliranFilsafat pra-Sokrates dan Sekolah Miletos Murid dariAnaximandros Anaximenes adalah seorang filsuf yang berasal dari Kota Miletos, sama seperti Thales dan Anaximandros.[1] Anaximene...

 

Jean de Tours

Jean de Tours Biographie Naissance XIe siècleTours Décès 1122 Évêque de l'Église catholique Ordination épiscopale Juillet 1088 par Lanfranc Évêque de Bath et Wells Gisa Godefroy Autres fonctions Fonction religieuse chapelain royal Fonction laïque médecin du roi (en) Notice sur www.catholic-hierarchy.org modifier  Jean de Tours (ou Jean de Villule) (né à Tours avant 1070, mort en 1122), médecin et chapelain de Guillaume le Conquérant, fut nommé évêque de Wells en Anglet...

Continuing the Conversation

Sculpture by Martin Dawe Continuing the ConversationContinuing the Conversation (2019)ArtistMartin DaweCompletion dateApril 5, 2018MediumBronze, graniteSubjectRosa ParksLocationGeorgia Tech, Atlanta, Georgia, United States Continuing the Conversation is a public sculpture honoring Rosa Parks in Atlanta, Georgia, United States. Located on the main campus of the Georgia Institute of Technology (Georgia Tech), the artwork was created by Martin Dawe and unveiled in 2018. History The idea for a mo...

 

Robert Chartoff

Robert ChartoffLahirRobert Irwin Chartoff[1](1933-08-26)26 Agustus 1933New York City, New York, ASMeninggal10 Juni 2015(2015-06-10) (umur 81)Santa Monica, California, ASKebangsaanAmerika SerikatPendidikanB.A. Union College J.D. Columbia University Law SchoolPekerjaanProduser FilmTahun aktif1967–2015Suami/istriPhyllis Raphael (bercerai) Vanessa Howard (1970-1983; bercerai) Jenny Weyman (1992-2015; kematiannya)Anakdengan Raphael: --Jenifer Chartoff --William Chartoff --Juli...

 

Izumiōtsu

City in Kansai, JapanIzumiōtsu 泉大津市CityIzumiōtsu City Hall FlagEmblemLocation of Izumiōtsu in Osaka PrefectureIzumiōtsuLocation in JapanCoordinates: 34°30′N 135°24′E / 34.500°N 135.400°E / 34.500; 135.400CountryJapanRegionKansaiPrefectureOsakaArea • Total13.73 km2 (5.30 sq mi)Population (January 1, 2022) • Total73,767 • Density5,400/km2 (14,000/sq mi)Time zoneUTC+09:00 (JST)City hall addr...

Синелобый амазон

Синелобый амазон Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:ЗавропсидыКласс:Пт�...

 

Bruce William Stillman

Australian biochemist and cancer researcher Bruce William StillmanBorn (1953-10-16) 16 October 1953 (age 70)Melbourne, AustraliaAlma materUniversity of Sydney(BSc [Hons. 1]),Australian National University (PhD)SpouseGrace StillmanChildren2AwardsAlfred P. Sloan, Jr. Prize,[1] Louisa Gross Horwitz Prize, Canada Gairdner International Award, Dr. H. P. Heineken PrizeScientific careerFieldsBiochemistryInstitutionsCold Spring Harbor Laboratory Bruce William Stillman AO FAA FRS (bo...

 

Фиолетовый цвет

Запрос «Сиреневый цвет» перенаправляется сюда. На эту тему нужно создать отдельную статью. Фиолетовый HEX 6900C6 RGB¹ (r, g, b) (105, 0, 198) CMYK (c, m, y, k) (46, 100, 0, 22) HSV² (h, s, v) (272°, 100%, 78%) Нормализовано к [0—255] Нормализовано к [0—100] Фиолетовый (#6900C6) Фиолетовый, светлый HEX 8000FF RGB¹ (r, g, b) (128, 0, 255) CMYK...

Aquatic science

Multidisciplinary study of freshwater and marine ecosystems Aquatic science is the study of the various bodies of water that make up our planet including oceanic and freshwater environments.[1] Aquatic scientists study the movement of water, the chemistry of water, aquatic organisms, aquatic ecosystems, the movement of materials in and out of aquatic ecosystems, and the use of water by humans, among other things. Aquatic scientists examine current processes as well as historic process...

 

Polybotus

City in the Roman province of Phrygia Salutaris Polybotus or Polybotos (Greek: Πολύβοτος) was a city in the Roman province of Phrygia Salutaris. Its site is located 3 miles (4.8 km) southwest of Bolvadin in Asiatic Turkey.[1][2] History This town is mentioned in the 6th century by Hierocles in his Synecdemus.[3] A map of Byzantine Anatolia with Polybotus located in the Anatolic Theme Due to the wide-ranging grasslands, the area was used as a mustering pla...

 

Fai rumore

Fai rumore Chanson de Diodato au Concours Eurovision de la chanson 2020extrait de l'album Che vita meravigliosa Sortie 7 février 2020 Durée 3:36 Langue Italien Genre Popballade Auteur-compositeur Diodato, Edwyn Roberts Label Carosello Chansons ayant remporté le Festival de Sanremo et chansons représentant la Italie au Concours Eurovision de la chanson Soldi(2019) Zitti e Buoni(2021)modifier Fai rumore (prononcé : [fai ruˈmoːre] ; en français : « Tu fais...

Klasemen medali Olimpiade Musim Panas 1992

Klasemen medaliOlimpiade Musim Panas 1992LokasiBarcelona, SpanyolIkhtisarPerolehan medali emas terbanyak Tim Persatuan (45)Perolehan jumlah medali terbanyak Tim Persatuan (112)← 1988 Klasemen medali1996 → Klasemen medali Olimpiade Musim Panas 1992 adalah klasemen medali selama pelaksanaan Olimpiade Musim Panas 1992. Olimpiade ini berlangsung di Barcelona, Spanyol sejak 25 Juli hingga 9 Agustus 1992. Terdapat 9.356 atlet dari 169 Komite Olimpiade Nasional (KON) ...

 

Château de Mehun-sur-Yèvre

Château de Mehun-sur-Yèvre Vue actuelle des ruines du château. Période ou style Gothique Architecte Guy de Dammartin Début construction 1367 XIVe siècle Propriétaire initial Famille de Courtenay Propriétaire actuel Commune Destination actuelle Musée Protection  Classé MH (1840) Coordonnées 47° 08′ 34″ nord, 2° 13′ 00″ est[1] Pays France Anciennes provinces de France Berry Région Centre-Val de Loire Département Cher Commune M...

 

2016年美國總統選舉

2016年美國總統選舉 ← 2012 2016年11月8日 2020 → 538個選舉人團席位獲勝需270票民意調查投票率55.7%[1][2] ▲ 0.8 %   获提名人 唐納·川普 希拉莉·克林頓 政党 共和黨 民主党 家鄉州 紐約州 紐約州 竞选搭档 迈克·彭斯 蒂姆·凱恩 选举人票 304[3][4][註 1] 227[5] 胜出州/省 30 + 緬-2 20 + DC 民選得票 62,984,828[6] 65,853,514[6]...

A Hard Day's Night (album)

A Hard Day's NightAlbum studio karya The BeatlesDirilis10 Juli 1964Direkam29 Januari, 25–27 Februari, 1 Maret & 1–4 Juni 1964, EMI Studios, London, dan Pathé Marconi Studios, ParisGenrePop rock,[1] pop[2]Durasi30:45LabelParlophoneProduserGeorge MartinKronologi The Beatles With the Beatles(1963)With the Beatles1963 A Hard Day's Night(1964) Beatles for Sale(1964)Beatles for Sale1964 Singel dalam album A Hard Day's Night Can't Buy Me Love/You Can't Do ThatDirilis...

 

جوزيف جوفري

جوزيف جوفري (بالفرنسية: Joseph Joffre)‏  معلومات شخصية اسم الولادة (بالفرنسية: Joseph Jacques Césaire Joffre)‏  الميلاد 12 يناير 1852(1852-01-12)فرنسا الوفاة 3 يناير 1931 (78 سنة)باريس، فرنسا مكان الدفن ليزانفاليد،  ولوفيسين  [لغات أخرى]‏  الجنسية  فرنسا عضو في الأكاديمية الفرنسية، ...

 

Universitas 21

Universitas 21Tanggal pendirian1997TipePendidikan dan penelitianKantor pusatBirmingham, Britania RayaWilayah layanan GlobalProvostJenny DixonSitus webU21 Universitas21 Universitas 21 (U21) adalah jaringan internasional universitas of riset.[1][2][3] Jaringan ini didirikan di Melbourne, Australia pada 1997 dengan 11 anggota, keanggotan telah berkembang hingga 29 universitas anggota di 19 negara dan teritori.[4][5] Universitas berkolaborasi pada pengalama...

Feminism in Canada

History of the feminist movement in CanadaPart of a series onFeminism History Feminist history History of feminism Women's history American British Canadian German Waves First Second Third Fourth Timelines Women's suffrage Muslim countries US Other women's rights Women's suffrage by country Austria Australia Canada Colombia India Japan Kuwait Liechtenstein New Zealand Spain Second Republic Francoist Switzerland United Kingdom Cayman Islands Wales United States states Intersectional variants F...

 

Orley Ashenfelter

American economist Orley AshenfelterBorn (1942-10-18) October 18, 1942 (age 81)San Francisco, California, USAcademic careerInstitutionPrinceton UniversityFieldLabor economics, applied econometricsAlma materPrinceton UniversityClaremont McKenna CollegeDoctoraladvisorAlbert ReesStephen GoldfeldDoctoralstudentsRobert LaLondeJohn DriffillHenry FarberJoseph AltonjiDavid E. BloomDavid Card[1]Janet CurrieJoshua AngristAwardsJacob Mincer Award (2005)IZA Prize in Labor Economics (200...