Can't install kernel because it asks for grub, can't install grub because it asks for kernel

I'm using Ubuntu Server 18.04. Today I ran the usual apt upgrade and got the following error:

Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
linux-image-4.15.0-23-generic : Depends: linux-modules-4.15.0-23-generic but it is not going to be installed
Recommends: grub-pc or
grub-efi-amd64 or
grub-efi-ia32 or
grub but it is not installable or
lilo but it is not going to be installed
E: Broken packages

So I tried to reinstall grub, but it won't let me:

Could not find /boot/grub/menu.lst file. Would you like /boot/grub/menu.lst generated for you? (y/N) /usr/sbin/update-grub-legacy-ec2: line 1101: read: read error: 0: Bad file descriptor
run-parts: /etc/kernel/postrm.d/x-grub-legacy-ec2 exited with return code 1
dpkg: error processing package linux-image-4.15.0-23-generic (--remove):
installed linux-image-4.15.0-23-generic package post-removal script subprocess returned error exit status 1
Removing linux-image-4.15.0-29-generic (4.15.0-29.31) …
/etc/kernel/postrm.d/initramfs-tools:
update-initramfs: Deleting /boot/initrd.img-4.15.0-29-generic
/etc/kernel/postrm.d/x-grub-legacy-ec2:
Searching for GRUB installation directory … found: /boot/grub
Searching for default file … found: /boot/grub/default
Testing for an existing GRUB menu.lst file …

Could not find /boot/grub/menu.lst file. Would you like /boot/grub/menu.lst generated for you? (y/N) /usr/sbin/update-grub-legacy-ec2: line 1101: read: read error: 0: Bad file descriptor
run-parts: /etc/kernel/postrm.d/x-grub-legacy-ec2 exited with return code 1
dpkg: error processing package linux-image-4.15.0-29-generic (--remove):
installed linux-image-4.15.0-29-generic package post-removal script subprocess returned error exit status 1
Errors were encountered while processing:
linux-image-4.15.0-23-generic
linux-image-4.15.0-29-generic
E: Sub-process /usr/bin/dpkg returned an error code (1)

I tried apt autoclean and apt autoremove, but the latter gives me this:

The following packages will be REMOVED:
linux-image-4.15.0-23-generic linux-image-4.15.0-29-generic
0 upgraded, 0 newly installed, 2 to remove and 0 not upgraded.
2 not fully installed or removed.

And then the same error above.

How do I fix that?