LL grammar
முறையான மொழிக் கோட்பாட்டில், எல்எல் இலக்கணம் என்பது ஒரு எல்எல் பாகுபடுத்தியால் பகுப்பாய்வு செய்யக்கூடிய ஒரு சூழல் இல்லாத இலக்கணமாகும், இது இடமிருந்து வலமாக உள்ளீட்டைப் பகுப்பாய்வு செய்கிறது, மேலும் வாக்கியத்தின் இடதுபுற வழித்தோன்றலை உருவாக்குகிறது (எனவே எல்எல், எல்ஆர் பாகுபடுத்தியுடன் ஒப்பிடும்போது வலதுபுற வழித்தோன்றலை உருவாக்குகிறது). எல்எல் இலக்கணத்தைக் கொண்ட ஒரு மொழி எல்எல் மொழி என்று அழைக்கப்படுகிறது. இவை முறையே தீர்மானகரமான சூழல்-இல்லாத இலக்கணங்கள் (டி. சி. எஃப். ஜி) மற்றும் தீர்மானகரமான சூழல்-இல்லாத மொழிகளின் (டி. சி. எஃப். எல்) துணைக்குழுக்களை உருவாக்குகின்றன. கொடுக்கப்பட்ட இலக்கணம் அல்லது மொழி "ஒரு எல். எல் இலக்கணம்/மொழி" அல்லது வெறுமனே "எல். எல்". என்று ஒருவர் கூறுகிறார், இது இந்த வகுப்பில் உள்ளது என்பதைக் குறிக்கிறது. எல்எல் பாகுபாடுகள் அட்டவணை அடிப்படையிலான பாகுபாடுகள் ஆகும், இது எல்ஆர் பாகுபாடுகளைப் போன்றது. எல்எல் இலக்கணங்களை ஒரு முன்கணிப்பு பாகுபடுத்தியால் துல்லியமாக பகுப்பாய்வு செய்யக்கூடியவை என்று வகைப்படுத்தலாம்-பின்தொடர்தல் இல்லாமல் ஒரு தொடர்ச்சியான வம்சாவளி பாகுபடுத்தல்-இவை கையால் எளிதில் எழுதப்படலாம். இந்தக் கட்டுரை எல். எல். இலக்கணங்களின் முறையான பண்புகளைப் பற்றியது; பகுப்பாய்விற்காக, எல். எல். பாகுபாடு அல்லது தொடர்ச்சியான வழித்தோன்றல் பாகுபாடு பார்க்கவும். முறையான வரையறை ஃபைனைட் கேஸ் ஒரு இயற்கையான எண்ணைக் கொடுத்தால், குறியீடுகள் வரை நீளமுள்ள ஒவ்வொரு முனைய சின்ன சரத்திற்கும், ஒவ்வொரு முடிவற்ற சின்னத்திற்கும், ஒவ்வொரு முனைய சின்ன சரத்திற்கும், அதிகபட்சம் ஒரு உற்பத்தி விதி இருந்தால், ஒரு சூழல் இல்லாத இலக்கணம் எல். எல் (கே) இலக்கணமாகும், அதாவது சில முனைய சின்ன சரங்களுக்கு, சரம் தொடக்க சின்னத்திலிருந்து பெறப்படலாம், முதலில் விதியைப் பயன்படுத்திய பிறகு பெறப்படலாம், மற்றும் ஒப்புக்கொள்ளும் மற்றும் ஒப்புக்கொள்ளும் முதல் சின்னங்கள். ஒரு மாற்று, ஆனால் அதற்கு சமமான, முறையான வரையறை பின்வருமாறுஃ ஒரு எல். எல் (கே) இலக்கணம், தன்னிச்சையான வழித்தோன்றல்களுக்கு, முதல் சின்னங்கள் அவற்றுடன் உடன்படும்போது, பின்னர். முறைசாரா முறையில், ஒரு பார்ஸர் அதன் இடதுபுற முனையத்துடன் பெறப்பட்டு, ஏற்கனவே உள்ளீட்டிலிருந்து நுகரப்படும்போது, அதைப் பார்த்து, தற்போதைய உள்ளீட்டின் அடுத்த சின்னங்களைப் பார்ப்பதன் மூலம், பார்ஸர் உற்பத்தி விதியை உறுதியாக அடையாளம் காண முடியும். கடந்த கால உள்ளீட்டைக் கருத்தில் கொள்ளாமல் கூட விதி அடையாளம் காண முடியும் போது, இலக்கணம் ஒரு வலுவான எல். எல் (கே) இலக்கணம் என்று அழைக்கப்படுகிறது. ஒரு வலுவான எல்எல் (கே) இலக்கணத்தின் முறையான வரையறையில், உலகளாவிய அளவீட்டாளர் தவிர்க்கப்பட்டுள்ளது, மேலும் "சிலருக்கு" அளவீட்டுடன் சேர்க்கப்படுகிறது. ஒவ்வொரு எல்எல் (கே) இலக்கணத்திற்கும், கட்டமைப்பு ரீதியாக சமமான வலுவான எல்எல் (கே) இலக்கணத்தை உருவாக்க முடியும். எல்எல் (கே) மொழிகளின் வகுப்பு கண்டிப்பாக அதிகரித்து வரும் தொகுப்புகளின் வரிசையை உருவாக்குகிறதுஃ எல்எல் (0) எல்எல் (1) எல்எல் (2). கொடுக்கப்பட்ட இலக்கணம் G என்பது LL (k) ஆக இருக்கிறதா என்பது தீர்மானிக்கக்கூடியது, ஆனால் ஒரு தன்னிச்சையான இலக்கணம் சில k க்கு LL (k) ஆக இருக்கிறதா என்பது தீர்மானிக்க முடியாதது. கொடுக்கப்பட்ட LR (k) இலக்கணமும் சில m க்கு LL (m) இலக்கணமாக இருந்தால் அது தீர்மானிக்கக்கூடியது. ஒவ்வொரு LL (k) இலக்கணமும் ஒரு LR (k) இலக்கணமாகும். ஒரு ε-இல்லாத LL (1) இலக்கணமும் ஒரு SLR (1) இலக்கணமாகும். வெற்று மற்றும் வெற்று அல்லாத வழித்தோன்றல்களைக் கொண்ட சின்னங்களைக் கொண்ட எல். எல். ஆர் (1) இலக்கணமும் ஒரு எல். ஏ. எல். ஆர் (1) இலக்கணமாகும். வெற்று வழித்தோன்றல் மட்டுமே கொண்ட சின்னங்களைக் கொண்ட எல்எல் (1) இலக்கணம் எல்ஏஎல்ஆர் (1) ஆக இருக்கலாம் அல்லது இல்லாமலும் இருக்கலாம். எல். எல். இலக்கணங்கள் இடது மறுநிகழ்வைக் கொண்ட விதிகளைக் கொண்டிருக்க முடியாது. ε-இல்லாத ஒவ்வொரு LL (k) இலக்கணத்தையும் கிரேபாக் இயல்பான வடிவத்தில் சமமான LL (k) இலக்கணமாக மாற்றலாம் (இது வரையறையின்படி இடது மறுபயன்பாட்டுடன் விதிகளைக் கொண்டிருக்கவில்லை). வழக்கமான வழக்கு ஒரு முனைய எழுத்துக்களாக இருக்கட்டும். ஒவ்வொரு மொழியும் வழக்கமானதாக இருந்தால் ஒரு பகிர்வு வழக்கமான பகிர்வு என்று அழைக்கப்படுகிறது. ஒரு சூழல் இல்லாத இலக்கணமாக இருக்கட்டும், அதன் வழக்கமான பகிர்வாக இருக்கட்டும். தன்னிச்சையான வழித்தோன்றல்களுக்கு அது ஒரு எல். எல் () இலக்கணம் என்று நாம் கூறுகிறோம். G என்பது LL () என்று ஒரு வழக்கமான பகிர்வு இருந்தால் ஒரு இலக்கணம் G என்பது LL-வழக்கமான (LLR) என்று கூறப்படுகிறது. ஒரு மொழி எல். எல்-வழக்கமான இலக்கணத்தால் உருவாக்கப்பட்டால் அது எல். எல்-வழக்கமானதாக இருக்கும். எல். எல். ஆர் இலக்கணங்கள் தெளிவற்றவை மற்றும் இடது-தொடர்ச்சியானதாக இருக்க முடியாது. ஒவ்வொரு எல்எல் (கே) இலக்கணமும் எல்எல்ஆர் ஆகும். ஒவ்வொரு எல். எல். (கே) இலக்கணமும் தீர்மானகரமானது, ஆனால் ஒரு எல். எல். ஆர் இலக்கணமும் உள்ளது, அது தீர்மானகரமானது அல்ல. எனவே எல்எல்ஆர் இலக்கணங்களின் வகை ஒவ்வொரு கேக்கும் எல்எல் (கே) கூட்டலை விட கண்டிப்பாக பெரியது. ஒரு வழக்கமான பகிர்வு கொடுக்கப்பட்டால், கொடுக்கப்பட்ட இலக்கணமானது எல்எல் () என்பதை தீர்மானிக்க முடியும். இருப்பினும், ஒரு தன்னிச்சையான இலக்கணம் ஜி என்பது எல். எல். ஆர் என்பதை தீர்மானிக்க முடியாது. ஒரு இலக்கணம் ஜி ஒரு வழக்கமான மொழியை உருவாக்குகிறதா என்பதை தீர்மானிப்பதே இதற்குக் காரணம், இது ஜி-க்கு ஒரு வழக்கமான பகிர்வைக் கண்டுபிடிக்க அவசியமாக இருக்கும், இது போஸ்ட் கடிதப் பிரச்சினையாக குறைக்கப்படலாம். ஒவ்வொரு எல்எல்ஆர் இலக்கணமும் எல்ஆர்-வழக்கமான (எல்ஆர்ஆர், எல்ஆர் (கே) இலக்கணங்களுக்கு சமமானது), ஆனால் எல்எல்ஆர் அல்லாத எல்ஆர் (1) இலக்கணங்கள் உள்ளன. வரலாற்று ரீதியாக, எல். எல். ஆர் இலக்கணங்கள் எல். ஆர். ஆர் இலக்கணங்களின் கண்டுபிடிப்பைப் பின்பற்றின. வழக்கமான உற்பத்தியின் நிகழ்வுகளை அடையாளம் கண்டு, பகுப்பாய்வை வலமிருந்து இடமாக மாற்ற ஒரு மூர் இயந்திரத்தை உருவாக்க முடியும். அதைச் செய்தவுடன், நேரியல் நேரத்தில் கடத்தப்பட்ட உள்ளீட்டைக் கையாள ஒரு எல்எல் (1) பாகுபாடு போதுமானது. எனவே, எல்எல்ஆர் பாகுபடுத்திகள் எல்எல் (கே) பாகுபடுத்திகளை விட கண்டிப்பாக பெரிய இலக்கணங்களின் ஒரு வகுப்பைக் கையாள முடியும், அதே நேரத்தில் சமமாக திறமையானவை. இருப்பினும் எல். எல். ஆர் கோட்பாட்டிற்கு பெரிய பயன்பாடுகள் எதுவும் இல்லை. ஒரு சாத்தியமான மற்றும் மிகவும் நம்பத்தகுந்த காரணம் என்னவென்றால், எல்எல் (கே) மற்றும் எல்ஆர் (கே) பாகுபடுத்திகளுக்கான உற்பத்தி வழிமுறைகள் இருந்தாலும், ஒரு வழக்கமான பகிர்வை முன்கூட்டியே கட்டமைக்காவிட்டால் எல்எல்ஆர்/எல்ஆர்ஆர் பாகுபடுத்தியை உருவாக்குவதில் உள்ள சிக்கல் தீர்மானிக்க முடியாதது. ஆனால் கொடுக்கப்பட்ட இலக்கணத்தில் பொருத்தமான வழக்கமான பகிர்வை உருவாக்குவதில் உள்ள சிக்கல் கூட தீர்மானிக்க முடியாதது. எளிய தீர்மானகரமான மொழிகள் ஒரு சூழல் இல்லாத இலக்கணம் எளிய தீர்மானகரமான அல்லது எளிமையான என்று அழைக்கப்படுகிறது, அது கிரேபாக் சாதாரண வடிவத்தில் இருந்தால் (அதாவது. ஒவ்வொரு விதிக்கும் வடிவம் உள்ளது), மேலும் ஒரே முனையத்திற்கு வெவ்வேறு வலது புறங்கள் எப்போதும் வெவ்வேறு முனையங்களுடன் தொடங்குகின்றன. ஒரு சரங்களின் தொகுப்பு ஒரு எளிய தீர்மானகரமான இலக்கணத்தைக் கொண்டிருந்தால், அது ஒரு எளிய தீர்மானகரமான அல்லது எளிமையான மொழி என்று அழைக்கப்படுகிறது. கிரேபாக் இயல்பான வடிவத்தில் ε-இல்லாத LL (1) இலக்கணத்தைக் கொண்ட மொழிகளின் வகுப்பு எளிய தீர்மானிக்கும் மொழிகளின் வகுப்பிற்கு சமம். இந்த மொழி வகுப்பில் ε இல்லாத வழக்கமான தொகுப்புகள் அடங்கும். சமன்பாடு இதற்கு தீர்மானிக்கக்கூடியது, அதே நேரத்தில் சேர்ப்பு இல்லை. பயன்பாடுகள் எல்எல் இலக்கணங்கள், குறிப்பாக எல்எல் (1) இலக்கணங்கள், மிகவும் நடைமுறை ஆர்வத்தைக் கொண்டுள்ளன, ஏனெனில் அவை எல்எல் பாகுபாடுகள் அல்லது தொடர்ச்சியான வம்சாவளிப் பாகுபாடுகள் மூலம் பகுப்பாய்வு செய்ய எளிதானவை, மேலும் இந்த காரணத்திற்காக எல்எல் (1) ஆக வடிவமைக்கப்பட்டுள்ளன. k இன் அதிக மதிப்புள்ள இலக்கணங்களை அடிப்படையாகக் கொண்ட மொழிகள் பாரம்பரியமாக பகுப்பாய்வு செய்வது கடினம் என்று கருதப்படுகின்றன, இருப்பினும் இது இப்போது குறைவான உண்மை, தன்னிச்சையான k க்கு LL (k) இலக்கணங்களை ஆதரிக்கும் பாகுபாடு ஜெனரேட்டர்கள் கிடைக்கின்றன மற்றும் பரவலாகப் பயன்படுத்தப்படுகின்றன. மேலும் பார்க்க LL (k) மற்றும் LL (*) பாகுபாடு செய்பவர்களின் பட்டியலுக்கான பாகுபாடு செய்பவர்களின் ஒப்பீடு குறிப்புகள் ஆதாரங்கள் மேலும் வாசிப்பு முறையான மொழிகள்